backtracking · Problem 1 of 2
Subsets
Return every subset of nums, which contains no duplicates.
subsets([1, 2]) -> [[], [2], [1], [1, 2]]
Order is fixed so the answer can be compared: for each element in order, first every subset that excludes it, then every subset that includes it. That is exactly what you get by taking the "skip" branch before the "take" branch at each step, so if your recursion is shaped that way the order falls out for free.
There are 2ⁿ subsets, so nothing here is faster than exponential. What the problem teaches is the shape — the decision tree, and undoing a choice on the way back up.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| subsets([]) | empty input has one subset | [[]] | — |
| subsets([1]) | a single element | [[],[1]] | — |
| subsets([1,2]) | two elements, skip before take | [[],[2],[1],[1,2]] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n · 2ⁿ)
- target space
- O(n) for the recursion, O(n · 2ⁿ) for the output
There are 2ⁿ subsets and copying each costs up to n, so the output itself is the dominant term — no algorithm can beat it, because producing the answer requires writing it down.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left