Subsets & Power Set Generation
Power Set generation enumerates all 2^n subsets of an n-element set using either recursive choose/skip backtracking or iterative bitmask enumeration, with clean duplicate handling.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Subsets & Power Set Generation
Every $n$-element set has exactly $2^n$ subsets (its Power Set). Generating all subsets—or all unique subsets when duplicates exist—is the foundational template for Backtracking and Bitmask Enumeration.
At a Glance
| Method | Time | Auxiliary Space | Handles Duplicates? |
| :--- | :---: | :---: | :---: |
| Backtracking (DFS) | $O(n \cdot 2^n)$ | $O(n)$ stack | Yes (sort + skip i > start && a[i] == a[i-1]) |
| Bitmask Enumeration (0..(1<<n)-1) | $O(n \cdot 2^n)$ | $O(1)$ extra | Best for distinct elements ($n \le 20$) |
---
Practice Problems
Easy
1. Generate All Unique Subsets (With Duplicates, LeetCode 90)
Given an array nums that may contain duplicates, return all unique subsets without duplicate sets.
Approach: Sort nums. In dfs(start), skip index i if i > start && nums[i] == nums[i - 1] so identical values at the same recursion level are only chosen once! Time: $O(n \cdot 2^n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> subsetsWithDup(std::vector<int> nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
std::vector<int> cur;
auto dfs = [&](auto& self, int start) -> void {
res.push_back(cur);
for (int i = start; i < static_cast<int>(nums.size()); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue;
cur.push_back(nums[i]);
self(self, i + 1);
cur.pop_back();
}
};
dfs(dfs, 0);
return res;
}
int main() {
auto s = subsetsWithDup({1, 2, 2});
std::cout << "Unique subsets: " << s.size() << "\n"; // 6: [],[1],[1,2],[1,2,2],[2],[2,2]
return 0;
}
</details>
---
Related Algorithms
- Bitmask DP — caches overlapping subset states instead of enumerating all paths.
- N-Queens — constrained backtracking.