Subsets (Power Set)
Subsets (LC 78)(opens leetcode.com)
You are given an array nums of different integers. Return every subset of it: the empty subset, every subset in between, and the whole array. No subset may appear twice. You may return the subsets in any order.
Subsets
elements ➔ every decision tree node is valid ➔ snapshot deep copy| 1 | from typing import List |
| 2 | |
| 3 | def subsets(nums: List[int]) -> List[List[int]]: |
| 4 | """Subsets (LC 78): every subset of nums, saved once at the node of the decision tree that builds it. |
| 5 | N = len(nums) and all values are different. |
| 6 | Time: O(N * 2^N) | Space: O(N) path + recursion stack, output not counted |
| 7 | """ |
| 8 | results: List[List[int]] = [] |
| 9 | path: List[int] = [] # the choices from the root to the current node, in order |
| 10 | |
| 11 | def backtrack(start: int) -> None: |
| 12 | # 1. Save This Node: |
| 13 | # Every node of the decision tree is a valid subset, so copy path into results |
| 14 | # as soon as the call starts, before trying any further choice. |
| 15 | results.append(list(path)) |
| 16 | |
| 17 | for i in range(start, len(nums)): |
| 18 | # 2. Choose, Explore, Un-choose: |
| 19 | # Add nums[i] to path, recurse forward so the next call only sees later |
| 20 | # indices, then remove nums[i] so the loop's next i tries its own branch. |
| 21 | path.append(nums[i]) |
| 22 | backtrack(i + 1) |
| 23 | path.pop() |
| 24 | |
| 25 | backtrack(0) |
| 26 | return results |
path always holds exactly the choices from the root to the current node, and every node is saved exactly once.Every node of the decision tree is a valid subset, so save a copy of path as soon as you enter backtrack. The loop only picks indices from start onward, so each subset is built in one order and saved once. The trap is saving path itself: path keeps changing with append and pop, so write results.append(list(path)), or every saved subset ends up empty.
See it run
Subsets, step by step
start 0path []saved 0
The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.
ithe index the loop is looking atstartthe first index this call may usei = startthe loop index is the first index of this callpaththe slot just added to pathundothe slot just removed from path
nums is [1, 2, 3]. path is empty, and backtrack(0) is about to run.
Gotcha 1 of 4
- The trap
Gotcha 1: Saving
pathinstead of a copylist(path)Mistakeresults.append(path)Fixresults.append(list(path))What happens:
results.append(path)stores the same list object every time. The code keeps changing that one list withappendandpop. At the end it is empty, so every saved subset is empty.Example: nums = [1, 2]Mistake: returns [[], [], [], []]Fix: returns [[], [1], [1, 2], [2]]
- The input has repeated values and the same subset must not be saved twice, as in Subsets II (LC 90): the loop also needs a sort and a skip test. See Subsets II
- Only subsets of one exact size (or one target sum) count, as in Combinations (LC 77): saving at every node would return every size. See Combinations
- You only test or count on/off patterns of a few fixed bits, as in Binary Watch (LC 401), instead of building each subset as a list. See Bitmask Subsets
Deep Dive
Why saving at every call finds every subset once
Backtracking walks a decision tree. Each call of backtrack is one node. The node's path is the list of choices made from the first call down to this call.
A subset is any group of items, so every path is already a valid subset. That is why the code saves list(path) as soon as backtrack starts, and does not wait for a leaf.
Each subset has exactly one path, because the choices are made in index order (see the next section). So each subset is saved once. For three different numbers, the tree has 8 nodes and the result has 8 subsets.
Why start removes repeated orderings
The loop in backtrack(start) tries only the indices from start to the end. After it picks i, it calls backtrack(i + 1). So the next pick always has a larger index than the last pick.
A group of indices has only one increasing order. For example, the numbers at indices 0 and 1 can be reached as [nums[0], nums[1]] only. The order [nums[1], nums[0]] would need a pick that goes back, and the loop never goes back.
This is the difference from Permutations (LC 46), where the order matters and the loop restarts at 0. A subset ignores the order, so one order is enough.
Choose, explore, un-choose: why path.pop() is needed
path is one list that every call shares. The call adds nums[i] with append, runs backtrack(i + 1), and then removes nums[i] with pop.
Without pop, the next value of i would start from a path that still holds the old choice. Every later subset would then contain a wrong item.
With pop, path is the same list after each branch as it was before the branch. This is the invariant: path always holds exactly the choices from the first call to the current call.
The cost: nodes times the copy
The tree has one node per subset, so N different numbers give 2^N nodes. Each node copies path, which costs up to O(N). The time is O(N * 2^N), and the call stack is O(N) deep. The saved lists are the output and are not counted.
For N = 20 different numbers, backtrack runs 1,048,576 times. A size of about 20 is the limit that the statement usually gives for this kind of problem.
If the input has repeated values, the same subset can be built twice. The card Subsets II shows how to skip the repeats.
60-Second Pitch
"Every node of the decision tree is a valid subset, so I save a copy of path when backtrack starts. The loop picks only indices from start onward, and the recursion goes to i + 1, so each subset is built in one order and saved once. I add nums[i] to path, recurse, and then pop it, so path is the same after each branch as before it. There are 2^N nodes, and each copies path in O(N). So the time is O(N * 2^N), and the stack is O(N) deep."
Common Questions
- Why do you save
pathat every call and not only when the index reaches the end? Every
pathis already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.- Why do you save
list(path)and notpath? pathis one list that the code keeps changing withappendandpop. Savingpathstores a reference to that list, and at the end it is empty.list(path)stores a copy of the choices at that moment.- What is the time and space complexity?
O(N * 2^N) time, because there are 2^N nodes and each one copies
pathin up toO(N). The space isO(N)forpathand the recursion stack. The output is not counted.- How does the answer change if the order inside a subset matters?
Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a
usedarray, as in Permutations (LC 46). Both use the same choose, explore, un-choose steps.- How can you make the answer without recursion?
Start with a list that holds the empty subset. For each number, add a copy of every existing subset with that number appended. After N numbers the list holds all 2^N subsets. The cost is the same, and the recursion is not needed.
SWE Reasoning
Spot it
- The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
- Every group is valid, including the empty group, so you save at every node and not only at a leaf.
- The order inside a group does not matter.
[1, 2]and[2, 1]count as one answer. - The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.
The invariant, step by step
backtrack(start)is called withpathholding the choices from the first call to this call. The first thing it does isresults.append(list(path)).- The loop runs
ifromstartto the end.path.append(nums[i])makes the choice, andbacktrack(i + 1)explores every subset that extends thispathwith later indices. path.pop()removes the choice.pathis now exactly what it was before step 2, so the nextistarts from a correctpath.- Each subset has one increasing order of indices, so each subset is saved once.
Traps
- Saving
pathand notlist(path). The code saves one list object and keeps changing it withappendandpop. For[1, 2], the result is four empty lists. backtrack(start + 1)instead ofbacktrack(i + 1). The next call then starts at the wrong index, and a value is picked twice. For[1, 2], the result contains[2, 2].- Forgetting
path.pop().pathkeeps the old choice, and every later subset contains a wrong item. - Saving only at a leaf. The code then misses every subset that does not use the last index. For
[1, 2], it returns only[1, 2]and[2].
Practice
Subsets (Power Set)
Subsets (LC 78)(opens leetcode.com)
You are given an array nums of different integers. Return every subset of it: the empty subset, every subset in between, and the whole array. No subset may appear twice. You may return the subsets in any order.
Subsets
elements ➔ every decision tree node is valid ➔ snapshot deep copy| 1 | from typing import List |
| 2 | |
| 3 | def subsets(nums: List[int]) -> List[List[int]]: |
| 4 | """Subsets (LC 78): every subset of nums, saved once at the node of the decision tree that builds it. |
| 5 | N = len(nums) and all values are different. |
| 6 | Time: O(N * 2^N) | Space: O(N) path + recursion stack, output not counted |
| 7 | """ |
| 8 | results: List[List[int]] = [] |
| 9 | path: List[int] = [] # the choices from the root to the current node, in order |
| 10 | |
| 11 | def backtrack(start: int) -> None: |
| 12 | # 1. Save This Node: |
| 13 | # Every node of the decision tree is a valid subset, so copy path into results |
| 14 | # as soon as the call starts, before trying any further choice. |
| 15 | results.append(list(path)) |
| 16 | |
| 17 | for i in range(start, len(nums)): |
| 18 | # 2. Choose, Explore, Un-choose: |
| 19 | # Add nums[i] to path, recurse forward so the next call only sees later |
| 20 | # indices, then remove nums[i] so the loop's next i tries its own branch. |
| 21 | path.append(nums[i]) |
| 22 | backtrack(i + 1) |
| 23 | path.pop() |
| 24 | |
| 25 | backtrack(0) |
| 26 | return results |
path always holds exactly the choices from the root to the current node, and every node is saved exactly once.Every node of the decision tree is a valid subset, so save a copy of path as soon as you enter backtrack. The loop only picks indices from start onward, so each subset is built in one order and saved once. The trap is saving path itself: path keeps changing with append and pop, so write results.append(list(path)), or every saved subset ends up empty.
See it run
Subsets, step by step
start 0path []saved 0
The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.
ithe index the loop is looking atstartthe first index this call may usei = startthe loop index is the first index of this callpaththe slot just added to pathundothe slot just removed from path
nums is [1, 2, 3]. path is empty, and backtrack(0) is about to run.
Gotcha 1 of 4
- The trap
Gotcha 1: Saving
pathinstead of a copylist(path)Mistakeresults.append(path)Fixresults.append(list(path))What happens:
results.append(path)stores the same list object every time. The code keeps changing that one list withappendandpop. At the end it is empty, so every saved subset is empty.Example: nums = [1, 2]Mistake: returns [[], [], [], []]Fix: returns [[], [1], [1, 2], [2]]
- The input has repeated values and the same subset must not be saved twice, as in Subsets II (LC 90): the loop also needs a sort and a skip test. See Subsets II
- Only subsets of one exact size (or one target sum) count, as in Combinations (LC 77): saving at every node would return every size. See Combinations
- You only test or count on/off patterns of a few fixed bits, as in Binary Watch (LC 401), instead of building each subset as a list. See Bitmask Subsets
Deep Dive
Why saving at every call finds every subset once
Backtracking walks a decision tree. Each call of backtrack is one node. The node's path is the list of choices made from the first call down to this call.
A subset is any group of items, so every path is already a valid subset. That is why the code saves list(path) as soon as backtrack starts, and does not wait for a leaf.
Each subset has exactly one path, because the choices are made in index order (see the next section). So each subset is saved once. For three different numbers, the tree has 8 nodes and the result has 8 subsets.
Why start removes repeated orderings
The loop in backtrack(start) tries only the indices from start to the end. After it picks i, it calls backtrack(i + 1). So the next pick always has a larger index than the last pick.
A group of indices has only one increasing order. For example, the numbers at indices 0 and 1 can be reached as [nums[0], nums[1]] only. The order [nums[1], nums[0]] would need a pick that goes back, and the loop never goes back.
This is the difference from Permutations (LC 46), where the order matters and the loop restarts at 0. A subset ignores the order, so one order is enough.
Choose, explore, un-choose: why path.pop() is needed
path is one list that every call shares. The call adds nums[i] with append, runs backtrack(i + 1), and then removes nums[i] with pop.
Without pop, the next value of i would start from a path that still holds the old choice. Every later subset would then contain a wrong item.
With pop, path is the same list after each branch as it was before the branch. This is the invariant: path always holds exactly the choices from the first call to the current call.
The cost: nodes times the copy
The tree has one node per subset, so N different numbers give 2^N nodes. Each node copies path, which costs up to O(N). The time is O(N * 2^N), and the call stack is O(N) deep. The saved lists are the output and are not counted.
For N = 20 different numbers, backtrack runs 1,048,576 times. A size of about 20 is the limit that the statement usually gives for this kind of problem.
If the input has repeated values, the same subset can be built twice. The card Subsets II shows how to skip the repeats.
60-Second Pitch
"Every node of the decision tree is a valid subset, so I save a copy of path when backtrack starts. The loop picks only indices from start onward, and the recursion goes to i + 1, so each subset is built in one order and saved once. I add nums[i] to path, recurse, and then pop it, so path is the same after each branch as before it. There are 2^N nodes, and each copies path in O(N). So the time is O(N * 2^N), and the stack is O(N) deep."
Common Questions
- Why do you save
pathat every call and not only when the index reaches the end? Every
pathis already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.- Why do you save
list(path)and notpath? pathis one list that the code keeps changing withappendandpop. Savingpathstores a reference to that list, and at the end it is empty.list(path)stores a copy of the choices at that moment.- What is the time and space complexity?
O(N * 2^N) time, because there are 2^N nodes and each one copies
pathin up toO(N). The space isO(N)forpathand the recursion stack. The output is not counted.- How does the answer change if the order inside a subset matters?
Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a
usedarray, as in Permutations (LC 46). Both use the same choose, explore, un-choose steps.- How can you make the answer without recursion?
Start with a list that holds the empty subset. For each number, add a copy of every existing subset with that number appended. After N numbers the list holds all 2^N subsets. The cost is the same, and the recursion is not needed.
SWE Reasoning
Spot it
- The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
- Every group is valid, including the empty group, so you save at every node and not only at a leaf.
- The order inside a group does not matter.
[1, 2]and[2, 1]count as one answer. - The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.
The invariant, step by step
backtrack(start)is called withpathholding the choices from the first call to this call. The first thing it does isresults.append(list(path)).- The loop runs
ifromstartto the end.path.append(nums[i])makes the choice, andbacktrack(i + 1)explores every subset that extends thispathwith later indices. path.pop()removes the choice.pathis now exactly what it was before step 2, so the nextistarts from a correctpath.- Each subset has one increasing order of indices, so each subset is saved once.
Traps
- Saving
pathand notlist(path). The code saves one list object and keeps changing it withappendandpop. For[1, 2], the result is four empty lists. backtrack(start + 1)instead ofbacktrack(i + 1). The next call then starts at the wrong index, and a value is picked twice. For[1, 2], the result contains[2, 2].- Forgetting
path.pop().pathkeeps the old choice, and every later subset contains a wrong item. - Saving only at a leaf. The code then misses every subset that does not use the last index. For
[1, 2], it returns only[1, 2]and[2].