Problem: https://leetcode.com/problems/subsets/
I have never done backtracking problems before and don’t really have the patience to try to come to the conclusions of those algorithms on my own at the moment, so I’ll just study what backtracking is by finding the answer to this problem and understanding what sort of techniques it employs, as dishonorable as that may be.
function subsets(nums: number[]): number[][] {
const result: number[][] = []
function backtrack(start: number, current: number[]): void {
result.push([...current])
for (let i = start; i < nums.length; i++){
current.push(nums[i])
backtrack(i + 1, current)
current.pop()
}
}
backtrack(0, [])
return result
}Phew. Okay. Xin Rui Li helped walk me through this, quite painfully, on a whiteboard. It took me a while, but I finally got it. It was sort of a combination of two groks.
The first is this:
This is me realizing the path that current follows. If you look at the code, you can see that current is only initialized once. Various snapshots of it are saved to results, and these are all those snapshots. We start at that first one [], and go from there. We start down this first leg of our journey.
Where you see x’s are where we’ve gotten to a place where i < 3 is no longer true so we stop going down that path. To be honest, I didn’t get all the x’s right, but I think they still illustrate the overall flow of the mutations of current and the places it has to “turn back”. It turns out this is a very difficult concept to illustrate, but Xin did a really good job of being patient and taking me through it.
I sort of understand how this made sense. It very much resembled DFS. But Xin pointed out it was really different in what it works with -
DFS uses a single node that is guaranteed to have either 1 or 2 branches. In this backtracking problem, we start with n number of nodes, and each of them has n paths to explore.
So instead of running two potential recursive functions like we could in a binary tree, we instead create this sort of flywheel of a for loop that spins up as many recursive functions as it needs to.
I think I may have skipped ahead in leetcode a bit though, because this felt like a really big jump to make. Not only are the paths dynamic, but they also are non-repeating. The backtracking part, which takes place in the very short line current.pop().
I understood this was supposed to point us backward somehow, but didn’t really understand how. In order to really feel this, or trust it, I needed to go from this line to the next place that current, which has now been modified to have one less element on the end because of pop, is used.
Which is, of course, the top of our for loop! We go back to the for-loop, and this is where we might push 3 if we had just popped off 2.
The backtrack instantiation we call before the pop function saves the [1,2,3] result for us. Then we proceed to pop off the 2 and see what happens if we keep going through the loop. It turns out that the next thing we get is [1, 3. Perfect!
In the end, I visualized this best with my body. It’s like I’m in the woods, and there’s a fork in the road. I take the right path to see what’s up there. Cool. I snap a pic maybe, and make a mental note. Then I go back to the fork. I see what’s on the other one. I get to explore each one this way by walking back to the fork.
At the same time, it is of course not like this at all - that’s a bit more like doing DFS on a binary tree.
But it doesn’t illustrate that visceral feeling of going back to try something else, and to do that you need to pop off the leg of the fork you just walked.
AH. This hurt a lot to learn. But! After a couple of hours of really studying it, I feel good about it. I was able to rewrite it from (shallow) memory in 2:22:
function subsets(nums: number[]): number[][] {
const result: number[][] = []
function backtrack(start: number, current: number[]){
result.push([...current])
for (let i = start; i < nums.length; i++){
current.push(nums[i])
backtrack(i+1, current)
current.pop()
}
}
backtrack(0, [])
return result
};I think I need to return to BFS and DFS and trees to grok those spaces a bit better - clearly backtracking was super foreign. A good metaphor is skipping a few steps on a staircase and needing to leap, but falling slightly times before making it.