Algorithm analysis backtracking

Backtracking is a trick 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, it will be solved when it tries to find that the existing step-by-step answers do not work correctlyCancel the calculations of the previous step or even the previous steps, and try to find the answer to the question again with other possible step-by-step solutions。In layman's terms, backtracking is an algorithm that goes back if it doesn't work.

The essence of backtracking is to exhaust all possibilities, and although it is sometimes possible to remove branches that are not possible answers at all by pruning, it is still essentially a brute-force enumeration algorithm. The backtracking method can be abstracted into a tree structure and is a tree with a finite height (n-fork tree). The backtracking method solves the problem of finding subsets in the set, and the size of the set is the fork of the tree, the depth of recursion, and the height of the tree.

Let's take finding a subset of the array [1,2,3] as an example:

The for loop is used to enumerate split points, in fact, the interval dp splits the interval is a similar practice.

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

This added to the result set is [1,2].

This addition to the result set is [2,3], and so on. There are six subsets, which are [1], 1,2], 1,2,3], 2], 2,3] and [3].

For the full permutation problem, the result set is added to the leaf node, but this is a matter of detail. After mastering the idea, everyone will learn Xi details will get twice the result with half the effort.

Let's take a look at how to write it.

Construct a spatial tree. Perform a traversal. If a boundary condition is encountered, the search is no longer down, but another chain. When the target condition is reached, the result is output. Pseudo**:

const visited = {}function dfs(i) visited[i] = true mark the current state as searched dosomething(i) do something to i for (according to the next state i can reach j) undo(i) restore i}

The technique of pruning is different for every question, but a simple rule isAvoid recursion that is simply not an answer

For example: 842Splitting the array into Fibonacci sequencesDescription:

Given a numeric string s, such as s ="123456579", which we can divide into Fibonacci sequences [123, 456, 579]. Formally, a Fibonacci sequence is a list of non-negative integers f, and satisfies: 0 <= f[i] <= 2 31 - 1, (i.e., each integer conforms to a 32-bit signed integer type);f.length >= 3；For all 0 <= i < flength - 2, both f[i] +f[i+1] = f[i+2] holds. Also, note that when splitting a string into small chunks, the number of each block must never start with zero, unless the block is the number 0 itself. Returns any set of Fibonacci sequence blocks split from s, or 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, therefore"01"，"2"，"3"Not a valid answer. Example 5: Input:"1101111"Output: [110, 1, 111]Explanation: Output [11,0,11,11] is also accepted. Hint: 1 < = slength < = 200 strings contains only numbers. 

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 pathappend(cur) ans = backtrack(i + 1, path) pruning 4 if len(ans) >2: return ans pathpop() return ans return backtrack(0, [

A major test point of pruning algorithm backtracking must be mastered.

For some backtracking problems, we can still use the Cartesian product to save the result in the return value instead of the path, so as to avoid the backtracking state, and since the result is in the return value, we can use memory recursion, and then optimize it to the form of dynamic programming.

Reference Topic: 140Word Splitting ii401Binary Watch 816Problems such as fuzzy coordinates are different from subsets and full permutations, and their combinations are regular, and we can use the Cartesian product formula to unite two or more subsets.

The essence of backtracking is to violently enumerate all possibilities. It should be noted that since the result set of backtracking is usually recorded on the path of the backtrace tree, if you do not undo the operation, the results may be different due to incorrect state after backtracking, so you need to undo the state when the recursion bubbles up to the bottom.

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