Print all Subsets (Power Set) of a given array

Posted by N.K. Chauhan on Mar 31, 2024

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).

Related


Find duplicates in O(n) time and O(1) extra space

Move all negative numbers to beginning of the array

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Find largest sum contiguous sub-array (Kadane's Algorithm)

Minimize the difference between the heights of smallest and highest tower

Find maximum and minimum element of an array

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Maximum Product Subarray (Modified Kadane's Algorithm)

Alternating +ve & -ve in array in O(1) time (maintaining order)

Program to right rotate an array by 'k' elements

Find duplicates in O(n) time and O(n) extra space.