Let's start with admitting this one fact: backtracking is hard. Or rather, *understanding it the first time* is hard.

Or, it's one of those concepts that you think you grasped it, only to realize later that you actually didn't.

We'll focus on one problem of finding the subsets of an array, but before that, let's imagine that we're walking along a path.

Then, we reach a fork. We pick one of the paths, and walk.

Then, we reach another fork in the path. We pick one of the paths again, and go on walking, then we reach a dead end. So, we *backtrack* to the last point we had a fork, then go through the other path that we didn't choose the first time.

Then we reach another dead end. So, we *backtrack* once more and realize that there are no other paths we can go from there. So we *backtrack* again, and explore the other path we didn't choose the first time we came to this point.

We reach yet another dead end, so we *backtrack*. We see that there are no more paths to explore, so we *backtrack* once more.

Now, we're at our starting point. There are no more paths left to explore, so we can stop walking.

It was a nice but tiring walk, and it went like this:

Now, let's take a look at an actual LeetCode problem.

#### Subsets

The description for Subsets says:

Given an integer array

`nums`

ofuniqueelements, returnall possible subsets (the power set).The solution set

must notcontain duplicate subsets. Return the solution inany order.

For example:

```
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
```

Or:

```
Input: nums = [0]
Output: [[], [0]]
```

Before diving into the solution code, let's take a look at how backtracking will work in this case. Let's call the `nums`

array `items`

instead:

For each item in `items`

, we have initially two choices: to include the item, or not to include it.

For each level
$n$
in this *decision tree*, we have the option to include the next item in `items`

. We have
$2^n$
possible subsets in total.

Let's simplify the example a bit, and say that `items`

is now `['a', 'b']`

(**We'll ignore the problem specifics for now**).

In this case, we can use backtracking like this:

```
function subsets(items: string[]) {
let result: string[][] = [];
let currentSubset: string[] = [];
function backtrack(idx: number) {
if (idx >= items.length) {
result.push([...currentSubset]);
return;
}
currentSubset.push(items[idx]);
backtrack(idx + 1);
currentSubset.pop();
backtrack(idx + 1);
}
backtrack(0);
return result;
}
console.log(subsets(['a', 'b']));
// -> [['a', 'b'], ['a'], ['b'], []]
```

Well, it looks simple at first glance, but what's going on?

One thing to notice is that we `pop`

from the `currentSubset`

, then call `backtrack`

. In our example of walking, that's the part we go back to our previous point, and continue our walk.

In the first animation, we indicated a dead end with a cross mark, and in this case, a dead end is the *base case* we reach.

It might still be tough to understand, so let's add some helpful `console.log`

s, and see the output:

```
function subsets(items: string[]) {
let result: string[][] = [];
let currentSubset: string[] = [];
function backtrack(idx: number) {
console.log(`======= this is backtrack(${arguments[0]}) =======`)
if (idx >= items.length) {
console.log(`idx is ${idx}, currentSubset is [${currentSubset}], adding it to result...`);
result.push([...currentSubset]);
console.log(`backtrack(${arguments[0]}) is returning...\n`)
return;
}
currentSubset.push(items[idx]);
console.log(`added ${items[idx]} to currentSubset, inside backtrack(${arguments[0]})`);
console.log(`calling backtrack(${idx + 1})...`)
backtrack(idx + 1);
let item = currentSubset.pop();
console.log(`popped ${item} from currentSubset, inside backtrack(${arguments[0]})`);
console.log(`calling backtrack(${idx + 1})...`)
backtrack(idx + 1);
console.log(`******* done with backtrack(${arguments[0]}) *******\n`);
}
backtrack(0);
return result;
}
console.log(subsets(['a', 'b']));
```

The output looks like this:

```
======= this is backtrack(0) =======
added a to currentSubset, inside backtrack(0)
calling backtrack(1)...
======= this is backtrack(1) =======
added b to currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [a,b], adding it to result...
backtrack(2) is returning...
popped b from currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [a], adding it to result...
backtrack(2) is returning...
******* done with backtrack(1) *******
popped a from currentSubset, inside backtrack(0)
calling backtrack(1)...
======= this is backtrack(1) =======
added b to currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [b], adding it to result...
backtrack(2) is returning...
popped b from currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [], adding it to result...
backtrack(2) is returning...
******* done with backtrack(1) *******
******* done with backtrack(0) *******
[ [ 'a', 'b' ], [ 'a' ], [ 'b' ], [] ]
```

If you noticed, *Add 'a'?* and

*Go ahead?*arrows on the first level are calls to

`backtrack(0)`

. *Add 'b'?* and

*Go ahead?*arrows on the second level are calls to

`backtrack(1)`

.`backtrack(2)`

calls are when we reach the "dead ends," in those cases, we add `currentSubset`

to the `result`

.

We always reach the base case in a `backtrack(2)`

call, obviously because it's only when the `idx`

equals `items.length`

.

*For a visualization of how the subsets function works, see https://rivea0.github.io/blog/leetcode-meditations-chapter-9-backtracking.*

*We modified the function in the above examples to work with strings, but in the actual solution we'll only deal with numbers, so in TypeScript, result and currentSubset will look like this:*

```
let result: number[][] = [];
let currentSubset: number[] = [];
```

*Also, the function parameter and return types are different:*

```
function subsets(nums: number[]): number[][] { ... }
```

*Otherwise, everything stays the same.*

#### Time and space complexity

A subset is, in the worst case, length
$n$
which is the length of our input. We'll have
$2^n$
subsets and since we also use the spread operator to copy `currentSubset`

, the time complexity will be
$O(n \cdot 2^n)$
. The space complexity is—*I think*—
$O(n \cdot 2^n)$
as well because of the recursive call stack (which is of depth `n`

), and the space needed for `result`

(which is in the worst case
$2^n$
).

Now it's time to take a deep breath, and maybe go on an actual walk. This has been a challenging concept to grasp, and perhaps the only thing that can make it click is a real walk in nature, with some backtracking along the way.

The first problem in this chapter is Combination Sum, until then, happy coding.

## Top comments (0)