AntInLoop

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.