Bit Manipulation — Subsets

↗ LeetCode: Subsets · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloombergApple

Given distinct integers nums, return all possible subsets (the power set).

Example 1 — nums=[1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Example 2 — nums=[0] → [[],[0]]

Constraints — 1 ≤ n ≤ 10. Brute recursive expansion is O(n·2ⁿ) = 10⁷ ops at n=20. Bitmask iteration over [0..2ⁿ) generating each subset directly is O(2ⁿ) = 10⁶ ops with better cache pattern.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Backtracking

Standard include/exclude recursion. O(2ⁿ · n).

Approach 2 — Iterative expansion

For each element, double the current answer by appending it to every existing subset.

java

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    out.add(new ArrayList<>());
    for (int x : nums) {
        int sz = out.size();
        for (int i = 0; i < sz; i++) {
            List<Integer> next = new ArrayList<>(out.get(i));
            next.add(x);
            out.add(next);
        }
    }
    return out;
}

Approach 3 — Bitmask enumeration (canonical)

Insight. Each subset corresponds to a bit pattern of length n. Iterate mask from 0 to 2ⁿ-1.

java

List<List<Integer>> subsetsBM(int[] nums) {
    int n = nums.length;
    List<List<Integer>> out = new ArrayList<>();
    for (int mask = 0; mask < 1 << n; mask++) {
        List<Integer> sub = new ArrayList<>();
        for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) sub.add(nums[i]);
        out.add(sub);
    }
    return out;
}

Execution Trace

Bitmask — nums=[1,2,3]

Complexity — Time O(2ⁿ · n); Space O(2ⁿ · n) for output.

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Backtracking	O(2ⁿ · n)	O(n) recursion	canonical
Iterative expansion	O(2ⁿ · n)	O(2ⁿ · n)	elegant
Bitmask	O(2ⁿ · n)	O(2ⁿ · n)	polish

When to use which

All subsets → any of the three.
All subsets with duplicate elements → sort + skip; see Subsets II.
Only subsets of size k → recurse with size arg; or DP.

✨AI Study CompanionBeta

Was this page helpful?

Bit Manipulation — Subsets ​

Approach 1 — Backtracking ​

Approach 2 — Iterative expansion ​

Approach 3 — Bitmask enumeration (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​