An array A is given, the task is to print all subsets of A using recursion. Every array of size n will have 2^n Subsets.
Example 1: Print subsets of {1, 2, 3}.
Input: new int[]{1, 2, 3}
Output:
[] [3] [2] [2, 3] [1] [1, 3] [1, 2] [1, 2, 3]
Example 2: Print subsets of {5, 2, 3, 4}.
Input: new int[]{5, 2, 3, 4}
Output:
[] [4] [3] [3, 4] [2] [2, 4] [2, 3] [2, 3, 4] [5] [5, 4] [5, 3] [5, 3, 4] [5, 2] [5, 2, 4] [5, 2, 3] [5, 2, 3, 4]
Solutions
Method 1: Recursion
As the pattern shows - to obtain any subset we are either choosing a number or dropping a number. This is exactly, what we need to do here, we will run the fn recursively twice, once including the current value in subset and other without including the current value in subset.
As soon as the iteration is complete we will print the sub-array; please note we have to pass a copy of "result" to non-including fn call, to avoid duplicate values.
Complexity
For every element two recursive case originates, so Time Complexity is O(2^n). For each element we need to store values in two subsets, so Space Complexity is O(2^n).