You are given nums, a list of distinct integers. Return every subset of it: every list you can
make by keeping some of the numbers, from none of them to all of them.
Each subset must appear exactly once. The subsets may come in any order, and so may the numbers inside each one.
Example 1
- Input
- nums = [4, 7, 1]
- Output
- [[], [4], [7], [1], [4, 7], [4, 1], [7, 1], [4, 7, 1]]
Example 2
- Input
- nums = [-2]
- Output
- [[], [-2]]
Constraints
numsholds 1 to 10 numbers.- Every number is between −10 and 10, and no number appears twice.
Show the pattern
Backtracking
Every number is either in a subset or out of it, so the subsets are the leaves of a tree of in-or-out choices. Backtracking walks that tree: make a choice, explore, then undo it.
See backtracking in a visualiserShow the approach
Backtrack over positions, keeping the subset being built in one list, chosen. A helper
explore(i) decides about nums[i]:
- When
i == len(nums), every number has been decided, so save a copy ofchosen. - Otherwise explore without
nums[i](callexplore(i + 1)), then appendnums[i], explore again, and pop it to undo the choice.
That reaches every combination of in-or-out choices exactly once: 2ⁿ subsets.
An iterative version works too: start from [[]], and for each number add a copy of every
subset so far with that number appended.
Time: O(n · 2ⁿ) · Space: O(n) besides the output