The problem
Given an array nums of different integers, return every subset — every selection of its elements, including none and all — in any order, without repeats.
Examples
01
- Input
nums = [1, 2, 3]
- Output
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
02
- Input
nums = [0]
- Output
[[], [0]]
Constraints
- 1 ≤ nums.length ≤ 10
- −10 ≤ nums[i] ≤ 10
- All the numbers are different.
The idea
Each element is either in a subset or not: two choices, n times, so there are 2ⁿ subsets. Picture a tree of decisions: at level i, one branch takes nums[i] and the other leaves it out; each leaf is one subset.
Backtracking walks that tree depth-first with one working list: add nums[i], explore everything below, remove it again (undo), then explore the branch without it. At the bottom, a copy of the list is an answer.
- Time
- O(n · 2ⁿ) — 2ⁿ subsets, each copied
- Space
- O(n) besides the answer — the working list and the calls
Solution · every language run against every case
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: out, cur = [], [] def choose(i): # decide about nums[i], then everything after it if i == len(nums): out.append(cur[:]) return cur.append(nums[i]) # with nums[i] choose(i + 1) cur.pop() # undo, then without it choose(i + 1) choose(0) return out