Given an array nums of distinct integers, return every possible subset (the power set), including the empty set and the full array. The answer must not contain the same subset twice. You may return the subsets in any order.
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All values are distinct
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
There are 2^n subsets, so any correct solution is at least O(n * 2^n) because the output itself is that large; the question is how to generate them cleanly without duplicates. Backtracking does it with the "choose, explore, un-choose" pattern: from position i, we try adding each later element nums[j], recurse to build bigger subsets starting after j, then remove nums[j] to try the next option. Because we only move forward, every subset is produced exactly once. An equally good alternative is the iterative build: start with [[]] and, for each number, add it to a copy of every existing subset.
Algorithm
- Create
resand an emptypath. - Define
backtrack(start): first add a copy ofpathtores. - For
jfromstartton - 1: appendnums[j]topath, callbacktrack(j + 1), then pop it. - Call
backtrack(0)and returnres.
O(n * 2^n)Space: O(n) recursion depth, plus the outputpath to the result (path[:] or new ArrayList<>(path)). Adding the list itself means every entry points to the same object, which ends up empty. Interviewers also like the bitmask version: numbers 0 to 2^n - 1, where bit j says whether nums[j] is in.class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res, path = [], []Β def backtrack(start): res.append(path[:]) # every path is a subset for j in range(start, len(nums)): path.append(nums[j]) # choose backtrack(j + 1) # explore path.pop() # un-chooseΒ backtrack(0) return res