How do you approach Subsets?

Use backtracking to generate all subsets.

What is the time complexity of Subsets?

Time complexity: O(n * 2^n). Space complexity: O(n) for recursion stack.

What are common mistakes on Subsets?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

Sitelet https://gitgood.dev/coding/subsets

gitGood.dev

← Back to problems

Subsets

MediumAlgorithms

Description

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2

Input: nums = [0]

Output: [[],[0]]

Constraints

- 1 <= nums.length <= 10 - -10 <= nums[i] <= 10 - All the numbers of nums are unique.

Subsets: approach, complexity and pitfalls

A medium backtracking problem, graded against 5 test cases (2 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 3-step hint ladder

Use backtracking to generate all subsets.
For each element, you have two choices: include it or exclude it.
Start with an empty subset and build up from there.

The optimal approach

Show the approach: Backtracking

For each element, decide to include or exclude it. Recursively build all combinations.

Time: O(n * 2^n)
Space: O(n) for recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.