Start practising

Subsets (2 choices per element)

Medium Recursion & Backtracking Pick / Not-Pick Original on LeetCode

Subsets (2 choices per element) is a medium recursion & backtracking problem solved with the pick / not-pick pattern. The best approach, optimal (pick / not-pick recursion), runs in O(n · 2ⁿ) time and O(n) space. Below are 2 approaches in Java, from brute force (bitmask) up.

Problem

Given an array nums of distinct integers, return every possible subset (the power set). The empty set counts, and the subsets can be in any order.

Examples

Example 1

Input
nums = [1, 2]
Output
[[], [1], [2], [1, 2]]

Example 2

Input
nums = [7]
Output
[[], [7]]

Constraints

  • 1 <= nums.length <= 10
  • All values in nums are distinct.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (bitmask)O(n · 2ⁿ)O(n)
Optimal (pick / not-pick recursion)O(n · 2ⁿ)O(n)

1Brute force (bitmask)

TimeO(n · 2ⁿ)2ⁿ masks, n bits checked for each.
SpaceO(n)Extra space besides the output.

Every subset matches an n-bit number: bit i set means nums[i] is included. Loop through all 2ⁿ masks and build each subset.

  1. For mask from 0 to 2ⁿ - 1:
  2. Add nums[i] for every bit i that is set.
Java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> cur = new ArrayList<>();
            for (int i = 0; i < n; i++)
                if ((mask & (1 << i)) != 0) cur.add(nums[i]);
            out.add(cur);
        }
        return out;
    }
}

2Optimal (pick / not-pick recursion)

TimeO(n · 2ⁿ)2ⁿ leaves, and copying each subset costs up to n. This matches the size of the output, so it can't be beaten.
SpaceO(n)Recursion depth and the path, not counting the output.

Recurse over the indices. At index i, first skip nums[i], then pick it, add it to the path, recurse and undo the choice. When i reaches n, the path is one complete subset.

  1. If i == n, add a copy of the path to the answer.
  2. Recurse without nums[i].
  3. Add nums[i], recurse, then remove it (backtrack).
Java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        build(nums, 0, new ArrayList<>(), out);
        return out;
    }

    private void build(int[] nums, int i, List<Integer> path, List<List<Integer>> out) {
        if (i == nums.length) {
            out.add(new ArrayList<>(path)); // copy, not the shared list
            return;
        }
        build(nums, i + 1, path, out);        // not pick
        path.add(nums[i]);                     // pick
        build(nums, i + 1, path, out);
        path.remove(path.size() - 1);          // undo
    }
}

Edge cases to test

  • Single element: the answer still includes the empty set

Hints

Hint 1

For each element there are exactly two choices. How many subsets does that give?

FAQ

What is the best time complexity for Subsets (2 choices per element)?

Optimal (pick / not-pick recursion) runs in O(n · 2ⁿ) time and O(n) extra space. 2ⁿ leaves, and copying each subset costs up to n. This matches the size of the output, so it can't be beaten.

Which pattern does Subsets (2 choices per element) use?

It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Generate all binary strings without consecutive 1's, Subsets II, Combinations.

Is there a brute force solution for Subsets (2 choices per element)?

Yes. Brute force (bitmask) takes O(n · 2ⁿ) time and O(n) space. Every subset matches an n-bit number: bit i set means nums[i] is included.

Which edge cases should I test for Subsets (2 choices per element)?

Single element: the answer still includes the empty set.