Subset Generation
Generating all subsets of a set of n elements can be done using bitmasking: iterate from 0 to 2^n - 1, and each bitmask represents a subset.
For a set of n elements, there are 2^n subsets. We can represent each subset by a bitmask of length n. If the i-th bit is 1, include the i-th element.
Java code to generate all subsets:
public static List> subsets(int[] nums) {
List> result = new ArrayList<>();
int n = nums.length;
for (int mask = 0; mask < (1 << n); mask++) {
List subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}
result.add(subset);
}
return result;
}
This technique is used in problems that require exploring all combinations, especially when n is small (≤ 20).
Two Minute Drill
- All subsets can be generated using bitmask from 0 to 2^n - 1.
- Each bitmask corresponds to a subset.
- Time O(2^n * n).
- Used in subset DP (e.g., traveling salesman).
Need more clarification?
Drop us an email at career@quipoinfotech.com