Skip to content

Backtracking ✅

Backtracking is a technique in DFS. The backtracking method uses the idea of ​​trial and error, which tries to solve a problem step by step. In the process of step-by-step problem solving, when it tries to find that the existing step-by-step answer cannot get an effective and correct answer, it will cancel the previous step or even the previous step of the calculation, and then pass other possibilities Try to find the answer to the question again.

In layman's terms, backtracking is an algorithm that just looks back if it fails.

The essence of backtracking is to exhaust all the possibilities, although sometimes it is possible to remove some branches that are impossible to answer through pruning, but in essence, it is still a brute force enumeration algorithm.

The backtracking method can be abstracted as a tree structure, and it is a tree with a finite height (N-ary tree). What the backtracking method solves is it finds a subset in the set. The size of the set is the fork tree of the tree, the depth of the recursion, and the height of the tree.

Take the example of finding a subset of the array [1,2,3]:

alt

The for loop is used to enumerate the division points. In fact, the interval dp division interval is a similar approach

In the above figure, we will perform the operation of adding to the result set at each node.

alt

For the gray nodes above, adding the result set is [1].

alt

This joining result set is [1,2].

alt

This added result set is [2,3], and so on. There are six subsets, namely [1], [1,2], [1,2,3], [2], [2,3] and [3].

For the full arrangement problem, it will be added to the result set at the leaf node, but this is all a matter of detail. Once you have mastered your thoughts, you will get twice the result with half the effort if you go to study the details.

Let's take a look at how to write specific code.

Algorithm flow

  1. Construct a space tree.
  2. Perform traversal.
  3. If boundary conditions are encountered, the search will no longer go down, but another chain will be searched.
  4. Reach the target condition and output the result.

Algorithm template

Fake code:

const visited = {}
function dfs(i) {
 if (satisfy certain conditions) {
  // Return the result or exit the search space
 }

 visited[i] = true // mark the current state as searched
 dosomething(i) // do some operations on i
 for (according to the next state j that i can reach) {
  if (!visited[j]) {// If state j has not been searched
   dfs(j)
  }
 }
 undo(i) // restore i
}

Pruning

Another test point for the backtracking question is pruning. Through proper pruning, time can be effectively reduced. For example, I optimized the time of Stone Game V from more than 900 ms to more than 500 ms through the pruning operation.

The technique of pruning is different for each question, but a simple principle is to avoid recursion that is impossible to answer at all.

For example:

Title description:

Given a number string S, such as S = "123456579", we can divide it into Fibonacci-like sequences [123, 456, 579].

Formally, the Fibonacci sequence is a list F of non-negative integers and satisfies:

0 <= F[i] <= 2^31-1, (that is, each integer conforms to the 32-bit signed integer type);
F.length >= 3;
For all 0 <= i <F.length-2, F[i] + F[i+1] = F[i+2] holds.
In addition, please note that when splitting the string into small blocks, the number of each block must not start with zero, unless the block is the number 0 itself.

Return any set of Fibonacci-like sequence blocks split from S, or [] if it cannot be split.

Example 1:

Input: "123456579"
Output: [123,456,579]
Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]
Example 3:

Input: "112358130"
Output: []
Explanation: This task cannot be completed.
Example 4:

Input: "0123"
Output: []
Explanation: The number of each block cannot start with zero, so "01", "2", and "3" are not valid answers.
Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11,0,11,11] is also accepted.

prompt:

1 <= S.length <= 200
The string S contains only numbers.

It can be solved by setting the retrospective template directly. But if you don't do proper pruning, it is easy to time out. Here I have performed four pruning operations, depending on the code.

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def backtrack(start, path):
            # Pruning 1
            if len(path)> 2 and path[-1] != path[-2] + path[-3]:
                return []
            if start >= len(S):
                if len(path)> 2:
                    return path
                return []

            cur = 0
            ans = []
            # Enumerate split points
            for i in range(start, len(S)):
                # Pruning 2
                if i> start and S[start] == ​​'0':
                    return []
                cur = cur * 10 + int(S[i])
                # Pruning 3
                if cur> 2**31-1:
                    return []
                path.append(cur)
                ans = backtrack(i + 1, path)
                # Pruning 4
                if len(ans)> 2:
                    return ans
                path.pop()
            return ans

        return backtrack(0, [])

The pruning process is represented in a diagram like this:

A major test point for the backtracking of the pruning algorithm, everyone must master it.

Cartesian Product

For some backtracking problems, we can still use the Cartesian product method to save the result in the return value instead of the path, which avoids the backtracking state, and because the result is in the return value, we can use memoized recursion, and then The optimization is in the form of dynamic programming.

Reference topic:

This type of problem is different from subsets and total permutations. Their combination is regular. We can use the Cartesian product formula to combine two or more subsets.

Classic topic

to sum up

The essence of backtracking is to enumerate all possible violently. It should be noted that since the result set of backtracking is usually recorded on the path of the backtracking tree, if the undo operation is not performed, the state may be incorrect after the backtracking and the results may be different. Therefore, it needs to bubble up from the bottom of the recursion. Time to cancel the state.

If you copy a piece of data every time you recursively process, then you don't need to undo the state, and the relative space complexity will increase.