Problem overview
The method subsets(nums) receives an array of distinct integers and returns every subset of it: every way to pick some of the numbers, from none (the empty subset) to all of them. Each subset keeps the order its numbers have in nums.
The order of the subsets matters too. Decide about the numbers one at a time, always trying "skip" before "take". Every subset without nums[0] comes before every subset with it; inside each of those groups, the subsets without nums[1] come first, and so on. For [1, 2, 3] the answer is:
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
The empty subset is always first and the whole array is always last. For [3, -1] the answer is [[], [-1], [3], [3, -1]]: the last subset is written [3, -1], in the order of nums, not sorted.
Approach: one decision per number
Every number is either in a subset or not, so an array of n numbers has 2^n subsets: 8 for three numbers, 1,024 for ten. No algorithm can return them faster than it can write them, so the question is how to list them without missing any or repeating any.
Backtracking does it by making one decision per index. At index i, first skip nums[i] and go on to index i + 1. Then take it: add it to the subset being built, go on to i + 1, and afterwards remove it again. When the index reaches the end of nums, every number has been decided, and the subset being built is complete, so a copy of it is saved.
The last step, removing the number, is what makes it "back" tracking: after exploring everything that contains nums[i], the search returns to the state it had before and the caller continues as if nothing happened. The same single list is reused for the whole search.
Trying skip before take produces the order the problem asks for. Here is the search on [1, 2], indented by depth:
i=0 skip
i=1 skip
save []
i=1 take 2 -> [2]
save [2]
i=0 take 1 -> [1]
i=1 skip
save [1]
i=1 take 2 -> [1,2]
save [1,2]
The saved subsets, in order, are [], [2], [1], [1, 2]. It's the same as counting in binary with a bit per number, 0 for skip and 1 for take, where the first number is the most significant bit.
Step by step
- Create
result, anumber[][]that starts empty. Each subset is a list of numbers, so the result is a list of lists. - Start the search with
this.backtrack(nums, 0, [], result): index 0 is the first number to decide about and the subset being built is empty. The helper adds toresult, so there is nothing to assign. - Return
result. The helper filled the same array. - Declare the helper
backtrack(nums, i, current, result), returningvoid.iis the index being decided andcurrentholds the numbers taken so far. - Stop at the end: when
i === nums.length, every number was skipped or taken. - Save a snapshot with
[...current]and return.currentkeeps changing as the search goes on, soresultneeds its own copy. - Skip first: call
backtrackfori + 1without touchingcurrent. Every subset withoutnums[i]comes out of this call, before any subset with it. - Take: push
nums[i]ontocurrent. Numbers are added in index order, so each subset keeps the order ofnums. - Call
backtrackagain fori + 1. This call finds every subset that containsnums[i]. - Undo with
pop(). The caller getscurrentback exactly as it was.
The solution in TypeScript
class Solution {
subsets(nums: number[]): number[][] {
const result: number[][] = [];
this.backtrack(nums, 0, [], result);
return result;
}
backtrack(nums: number[], i: number, current: number[], result: number[][]): void {
if (i === nums.length) {
result.push([...current]);
return;
}
this.backtrack(nums, i + 1, current, result);
current.push(nums[i]);
this.backtrack(nums, i + 1, current, result);
current.pop();
}
}
TypeScript details worth knowing
Arrays are references. current is one array shared by every call. If the code pushed current itself onto result, result would hold many references to that single array, and since the search finishes by popping everything, they would all end up showing its final contents. The spread [...current] creates a new array with the same numbers, which stays as it was. For example, after current.push(1), result.push(current) and current.pop(), result is [[]], while pushing [...current] instead leaves [[1]].
const and arrays. const result means the name always refers to the same array. The array itself can still grow, which is what push does.
this.. backtrack is a method of the class, so it is called as this.backtrack(...). Inside the class a bare backtrack(...) would not be found.
The types, such as number[][] and void, are checked by the compiler and then erased from the JavaScript it produces. The method works the same without them.
Complexity
Time: O(n · 2^n). The search ends in 2^n complete subsets, and saving each one copies up to n numbers. The calls on the way down add only about 2^(n+1) in all, which doesn't change the bound.
Space: O(n) besides the answer. There is one current list of at most n numbers and a chain of at most n + 1 calls, one per index. The answer itself holds 2^n subsets and is not counted.
Edge cases and common mistakes
- One number.
[0]gives[[], [0]]: without it, then with it. - Forgetting the copy. Pushing
currentdirectly stores the same array again and again; the result ends up with the wrong contents. - Forgetting
pop(). The skip branch of the next call would still see the number, and later subsets would contain numbers they shouldn't. - Taking before skipping. The subsets are all there, but in a different order than the lesson expects. Skip first.
- Reordering numbers. Each subset should keep the order of
nums. Because the index only goes forward, it does. - Empty subset. The empty subset is part of the answer, and it is the first one saved, when every number has been skipped.
Testing
The lesson's code gives these results:
subsets([1, 2, 3]) -> [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
subsets([0]) -> [[],[0]]
subsets([3, -1]) -> [[],[-1],[3],[3,-1]]
For the numbers 1 to 10 it returns 1,024 subsets.
