DSA problem
Subsets
Given an integer array nums of n unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets and may be returned in any order. For an input of length n the power set has exactly 2^n elements, including the empty set and the full set itself.
A natural way to enumerate subsets is bit masking — iterate mask from 0 to 2^n - 1 and include nums[i] whenever bit i of mask is set. That works and is even branch-free, but the more compositional and easier-to-extend approach is backtracking, especially because it generalizes to combinations and to inputs with duplicates.
In the backtracking formulation we walk a recursion tree where, at index i, we have two choices: include nums[i] in the current subset or skip it. By always advancing the index in the next call, no element is considered twice and no duplicate subsets are produced. A cleaner variant uses a single loop: backtrack(start) adds the current path to the results, then iterates i from start to n - 1 picking nums[i] and recursing on i + 1.
The key implementation detail is to snapshot path at every node — not just at the leaves — because every node in the tree represents a valid subset. The trade-off is O(n * 2^n) total time (we generate 2^n subsets, each costing up to O(n) to copy) and O(n) recursion depth plus O(n) for the working path, with the output itself accounting for O(n * 2^n) extra memory.
Examples
nums = [1,2,3][[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]nums = [0][[],[0]]nums = [1,2][[],[1],[1,2],[2]]Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
- The solution set must not contain duplicate subsets.
- You may return the subsets in any order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.