Problem overview
The function subsets(nums: IntArray): List<List<Int>> receives an array of distinct integers and returns every subset: every way to pick some of the numbers, from none (the empty subset) to all of them. Each subset lists its numbers in the order they have in nums.
The order of the subsets is fixed too. You decide about the numbers one at a time, skipping before taking: every subset without nums[0] comes before every subset with it, and inside each group the same rule applies to nums[1], then nums[2], and so on. For nums = [1, 2, 3] the result is:
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
The first four subsets skip 1 and the last four take it. For [0] the result is [[], [0]], and for [3, -1] it is [[], [-1], [3], [3, -1]]: the last subset keeps the order of nums, so it isn't sorted.
Approach: one skip-or-take choice per number
A subset is the answer to one yes/no question per number: is it in or out? With n numbers that makes 2^n subsets, so any solution has to produce exponentially many lists. The goal is to produce each exactly once, in the required order.
Backtracking does this by walking through nums by index and keeping a list current of the numbers taken so far. At index i it makes two recursive calls, each moving on to i + 1:
- Skip
nums[i]: leavecurrentas it is. - Take
nums[i]: add it tocurrent, recurse, and then remove it again.
When i reaches the end of nums, every number has been skipped or taken, and current is a finished subset. Doing the skip call first gives exactly the order the lesson wants. It is the same pattern as writing binary strings: a subset is a string of n bits, 0 for skip and 1 for take, and the subsets come out in the order of those strings.
The removal after the "take" call is what makes the pattern work with one shared list. Each call gets current in some state and must hand it back in that same state, so the caller can go on with its next choice. That undo is the "back" in backtracking.
Here is the recursion on nums = [1, 2], with deeper calls indented:
i=0 skip 1, current=[]
i=1 skip 2, current=[]
i=2 save []
i=1 take 2, current=[2]
i=2 save [2]
i=0 take 1, current=[1]
i=1 skip 2, current=[1]
i=2 save [1]
i=1 take 2, current=[1, 2]
i=2 save [1, 2]
The saved subsets are [], [2], [1], [1, 2], in the required order.
Step by step
- Create
resultas an emptymutableListOf<List<Int>>(). It collects the subsets, each of which is itself a list. - Start the search by calling
backtrackwithnums, index 0, an emptymutableListOf()for the subset in progress, andresult. At the start nothing is decided yet. - Return
result. The helper has added to this same list, so it holds every subset after the call. - Write the helper's signature. It takes the array, the index
ito decide about, thecurrentlist andresult, and returns nothing. - Check for the end. When
i == nums.size, every number has been decided. - Save a snapshot and return.
current.toList()makes a new list with the same numbers, becausecurrentkeeps changing as the search goes on. - Skip first. Recurse to
i + 1without touchingcurrent. This finds every subset that leaves outnums[i]. - Take. Add
nums[i]to the end ofcurrent. Numbers are added in index order, so each subset keeps the order ofnums. - Recurse again to
i + 1, now withnums[i]incurrent. This finds every subset that contains it. - Undo the choice with
removeAt(current.size - 1), which removes the last element, socurrentis what this call received.
The solution in Kotlin
class Solution {
fun subsets(nums: IntArray): List<List<Int>> {
val result = mutableListOf<List<Int>>()
backtrack(nums, 0, mutableListOf(), result)
return result
}
fun backtrack(nums: IntArray, i: Int, current: MutableList<Int>, result: MutableList<List<Int>>) {
if (i == nums.size) {
result.add(current.toList())
return
}
backtrack(nums, i + 1, current, result)
current.add(nums[i])
backtrack(nums, i + 1, current, result)
current.removeAt(current.size - 1)
}
}
Kotlin details worth a look:
- Read-only and mutable lists.
List<Int>is a read-only view, whileMutableList<Int>hasaddandremoveAt. The helper takes mutable lists because it changes them. AMutableListis also aList, soresult.add(current.toList())fits aMutableList<List<Int>>, and returningresultasList<List<Int>>needs no conversion. - Why
toList()matters. Without it,result.add(current)stores the very list the search keeps changing. By the end of the search,currentis empty again, so every saved entry shows the same empty list: for[1, 2, 3]the output becomes eight copies of[]. A copy freezes the subset at the moment it was complete. - Type inference.
mutableListOf()in the first call needs no type argument, because the parameter typeMutableList<Int>tells the compiler it holdsInts. removeAtversusremove. On aMutableList<Int>,removeAt(index)removes by position andremove(element)removes by value. With[10, 20, 30],remove(30)gives[10, 20]whileremoveAt(0)gives[20, 30]. Here the code wants the last position, so it usesremoveAt.- Reading the array.
numsis never changed, so every call can share it.
Complexity
Time: O(n · 2^n). The recursion makes a binary tree of depth n with 2^n leaves, and the whole tree has fewer than 2^(n+1) calls. Each leaf copies current, which takes up to n steps. Adding and removing a number is constant time.
Space: O(n) extra, not counting the answer. The list current holds at most n numbers, and the recursion is at most n + 1 calls deep. The answer itself holds 2^n lists, which is unavoidable.
Edge cases and common mistakes
- The empty subset. It is always first, because skipping every number is the first leaf the search reaches. Dropping it from the result is a mistake.
- One number.
[0]gives[[], [0]]: two subsets, without the number and then with it. - Taking before skipping. The subsets are all there, but in a different order from the one the lesson requires, so the tests fail.
- Forgetting to undo. If
removeAtis missing, numbers pile up incurrentand later subsets contain numbers they shouldn't. - Saving
currentwithout copying it. The saved entries are all the same list and end up empty. - Not keeping the order of
nums. For[3, -1]the last subset is[3, -1], not[-1, 3]. Adding numbers as the index grows keeps that order without any sorting. - Size. A ten-number input produces 1024 subsets. The count doubles with every extra number.
Testing
nums = [1, 2, 3]gives[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]].nums = [0]gives[[], [0]].nums = [3, -1]gives[[], [-1], [3], [3, -1]].- An array with the numbers 1 to 10 gives a list of 1024 subsets.
