Subsets Or Powerset, A Faang Interview Question

In this article, we discuss the subsets of a given input. This is one of the most popular questions asked in coding interviews.
Apple, Microsoft, Amazon, and Facebook are some companies that have asked about this in their coding interviews.
Problem statement
We need to write a program that finds all possible subsets (the power set) of a given input. The solution set must not contain duplicate subsets.
Example 1
Input: [1, 2, 3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2
Input: [100]
Output: [[], [100]]
Explanation
The subsets of any given input are equal to its power set. If input n = 3
, then powerset => 2n
ββ= 23
= 8
. We assume that the input has a length greater than or equal to 1
.
Hint: We can use the left-shift operator to achieve this.
Thought process
This program finds the power set of a given input using bitwise operations.
In general, if we have n
elements, then the subsets are 2βn
. Therefore, for every possible case of having at least two elements, we can see that an element is present and not present in the subsets.
Letβs think of an iterative solution that uses bitwise operators and generates the powerset.
Here is how we generate each subset using the outer-loop variable counter
. The following table indicates how the value is generated based on the counter
input.
HTML Table
Counter (in decimal) | Counter (in binary) | Subset |
---|---|---|
0 | 000 | [] |
1 | 001 | [1] |
2 | 010 | [2] |
3 | 011 | [1, 2] |
4 | 100 | [3] |
5 | 101 | [1, 3] |
6 | 110 | [2, 3] |
7 | 111 | [1, 2, 3] |
Algorithm
We need to consider a counter
variable that starts from 0
to 2
βn
ββ - 1
. We consider the binary representation for every value and use the set bits in the binary representation to generate the corresponding subsets.
- If all set bits are
0
, the corresponding subset is empty[]
. - If the last bit is
1
, we put1
in the subset as[1]
.
Steps
We use two loops here. The outer loop starts from 0
to 2βnββ - 1
, and the inner loop continues to input array length n
.
In the inner loop, we conditionally check (counter & (1 << j)) != 0)
. If yes, then we print the corresponding element from an array.
Solution
import java.util.ArrayList;
import java.util.List;
class Subsets {
public static void main(String[] args) {
int[] input = {1, 2, 3};
System.out.println(subsets(input));
}
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
int powSize = (int) Math.pow(2, n);
for (int i = 0; i < powSize; i++) {
List<Integer> val = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
val.add(nums[j]);
}
}
result.add(val);
}
return result;
}
}
Complexity analysis
Time Complexity: O(n*2^n^)
: The time complexity is n
times the powerset.
Space Complexity:O(2n)
: We storing 2βn
ββ subset elements in an array. So, the extra space is directly proportional to O(2nββ)
.
I have also written a course on how to solve problems using bit manipulation. You can visit it here: Master Bit Manipulation for Coding Interviews.