Problem overview
The method Subsets receives an int[] called nums of distinct numbers and returns every subset: every way to pick some of the numbers, from none (the empty subset) to all of them. The result is a List<List<int>>, one inner list per subset.
Two rules fix the output exactly. Each subset lists its numbers in the order they have in nums, and the subsets come in the order you get by deciding about the numbers one at a time, skipping before taking. For {1, 2, 3} the result is [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]: the first four subsets skip 1, the last four take it. For {3, -1} it is [[],[-1],[3],[3,-1]], so the last subset is written in the order of nums, not sorted.
Approach: skip or take, one number at a time
A subset is the answer to one yes/no question per number: is it in or out? With n numbers that is n decisions, so there are 2^n subsets. Backtracking walks through all of those decision sequences.
The search keeps a list current of the numbers taken so far and an index i of the number to decide about. At index i it tries two branches, in this order:
- Skip
nums[i]: go on toi + 1withcurrentunchanged. - Take it: add it to
current, go on toi + 1, then remove it again.
When i reaches the end of nums, every number has been decided and current is one finished subset. Trying skip before take puts every subset without nums[0] before every subset with it, then the same inside each group for nums[1], and so on, which is the order the lesson asks for. It is the same as counting in binary with 0 for skip and 1 for take.
The removal after the take branch is the "back" in backtracking. The caller continues with current exactly as it was before the call, so one list can be shared by the whole search.
Step by step
- Create
result, an emptyList<List<int>>. Each subset is itself a list of numbers, so the outer list holds lists. - Start the search with
Backtrack(nums, 0, new List<int>(), result): no number is decided yet, the subset is empty, and every number from index 0 on can be skipped or taken. - Return
result.Backtrackadded to this same list, so it now holds every subset. - Write
Backtrackas apublic voidmethod with the parametersnums,i,currentandresult. Each call decides aboutnums[i]and calls itself for the next index. - Stop at the end. If
i == nums.Length, add a copy ofcurrenttoresultandreturn. The copy isnew List<int>(current). - Skip: call
Backtrack(nums, i + 1, current, result)without touchingcurrent. - Take:
current.Add(nums[i]), then callBacktrackwithi + 1again. This timecurrentholdsnums[i]. - Undo:
current.RemoveAt(current.Count - 1)removes the number just added, socurrentis again what this call received.
The solution in C#
class Solution {
public List<List<int>> Subsets(int[] nums) {
List<List<int>> result = new List<List<int>>();
Backtrack(nums, 0, new List<int>(), result);
return result;
}
public void Backtrack(int[] nums, int i, List<int> current, List<List<int>> result) {
if (i == nums.Length) {
result.Add(new List<int>(current));
return;
}
Backtrack(nums, i + 1, current, result);
current.Add(nums[i]);
Backtrack(nums, i + 1, current, result);
current.RemoveAt(current.Count - 1);
}
}
The C# details worth knowing:
- Why the copy matters. A
List<int>is a reference type, so addingcurrentitself toresultwould store a reference to the same object each time. The search keeps changing that object, and once everything is undone it is empty, so every stored entry would show an empty list. Addingcurrentto a list and then changing it changes what the outer list shows: afteral.Add(cur)andcur.Add(2)on a list that held only 1, the outer list prints[[1,2]].new List<int>(current)copies the numbers into a separate list. - Lists and arrays.
nums.Lengthis the length of an array, while a list hasCount. Mixing them up is a compile error. RemoveAttakes an index.current.RemoveAt(current.Count - 1)removes the last element.Remove(value)would search for a value instead, and an index of-1would throwArgumentOutOfRangeException.- Methods can call each other in any order.
SubsetsusesBacktrackbefore its definition appears, which is fine inside a class. - The helper's types. Because
List<T>is a class, passingcurrentandresulttoBacktrackpasses references, not copies. That is why the helper can fill the caller'sresultwithout returning anything.
Complexity
Time: O(n · 2^n). The recursion has 2^n leaves, one per subset, and the number of calls in total is about twice that. Copying a finished subset takes up to n steps, which gives the factor n.
Space: O(n) beyond the answer. current holds at most n numbers and the recursion is at most n + 1 calls deep. The answer itself holds 2^n lists and takes far more space than that, which is not counted as extra space.
Edge cases and common mistakes
- One number.
{0}gives[[],[0]]: without it, then with it. - The empty subset is always first and the full list always last, because skipping comes first at every index.
- Negative numbers.
{3, -1}gives[[],[-1],[3],[3,-1]]. Nothing is sorted: each subset keeps the order ofnums. - Forgetting the copy. Every entry of
resultbecomes the same list, which ends up empty. - Forgetting the undo.
currentkeeps growing, so later subsets contain numbers that were never taken in their branch. - Taking before skipping. The subsets are all there, but in the wrong order for the lesson's tests.
Testing
{1, 2, 3}gives[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]].{0}gives[[],[0]].{3, -1}gives[[],[-1],[3],[3,-1]].- Five numbers give 32 subsets, and ten give 1024.
