Print all Subsets (Power Set) of a given array

Posted by N.K. Chauhan on Jan 20, 2023

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


Program to print Intersection of two sorted arrays

Find a triplet in an array that sums to a given number

Longest substring without repeating characters

Print all possible permutations of an Array in O(1) space

Count the number of inversions in an array - in O(n log n) time

Two Sum - return index of a pair of array elements with a given sum

Merge two sorted arrays in O(1) space

Program to print Union of two sorted arrays

Rain water trapping problem - O(n) time & O(n) space

Word Break Problem (Using HashMap and DP)