[Leetcode] Backtracking回溯法解题思路

碎碎念: 最近终于开始刷middle的题了，对于我这个小渣渣确实有点难度，经常一两个小时写出一道题来。在开始写的几道题中，发现大神在discuss中用到回溯法(Backtracking)的概率明显增大。感觉如果要顺利的把题刷下去，必须先要把做的几道题题总结一下。

先放上参考的web：

回溯法是什么

回溯法跟DFS（深度优先搜索）的思想几乎一致，过程都是穷举所有可能的情况。前者是一种找路方法，搜索的时候走不通就回头换条路继续走，后者是一种开路策略，就是一条道先走到头，再往回走移步换一条路都走到头，直到所有路都被走遍。

既然说了，这是一种穷举法，也就是把所有的结果都列出来，那么这就基本上跟最优的方法背道而驰，至少时间复杂度是这样。但是不排除只能用这种方法解决的题目。

不过，该方法跟暴力（brute force）还是有一点区别的，至少动了脑子。

回溯法通常用递归实现，因为换条路继续走的时候换的那条路又是一条新的子路。

回溯法何时用

高人说，如果你发现问题如果不穷举一下就没办法知道答案，就可以用回溯了。

一般回溯问题分三种：

Find a path to success 有没有解

Find all paths to success 求所有解

求所有解的个数

求所有解的具体信息

3.Find the best path to success 求最优解

理解回溯：

回溯可以抽象为一棵树，我们的目标可以是找这个树有没有good leaf，也可以是问有多少个good leaf，也可以是找这些good leaf都在哪，也可以问哪个good leaf最好，分别对应上面所说回溯的问题分类。

回溯问题解决

有了之前对三个问题的分类，接下来就分别看看每个问题的初步解决方案。

有没有解

boolean solve(Node n) {

    if n is a leaf node {

        if the leaf is a goal node, return true

        else return false

    } else {

        for each child c of n {

            if solve(c) succeeds, return true

        }

        return false

    }

}

这是一个典型的DFS的解决方案，目的只在于遍历所有的情况，如果有满足条件的情况则返回True

求所有解的个数

void solve(Node n) {

    if n is a leaf node {

        if the leaf is a goal node, count++, return;

        else return

    } else {

        for each child c of n {

            solve(c)

        }

    }

}

列举所有解

这是文章的重点：

sol = []

def find_all(s, index, path, sol):

    if leaf node: ## (via index)

        if satisfy?(path):

            sol.append(path)

        return

    else:

        for c in choice():

            find_all(s[..:..], ,index+/-1, path+c, sol)

对于寻找存在的所有解的问题，一般不仅需要找到所有解，还要求找到的解不能重复。

这样看着思路虽然简单，但是在实际运用过程中需要根据题目进行改动，下面举一个例子：

eg1: 18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

下面的代码就是一个实际的回溯操作。

这个回溯函数有5个参数，nums是剩余数据，target是需要达到的条件，N为每层的遍历次数。

result当前处理的结果。results为全局结果。

这是一个典型的python解法，之后很多题都是套这个模版，我发现。

def fourSum(self, nums, target):

    def findNsum(nums, target, N, result, results):

        if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination

            return

        if N == 2: # two pointers solve sorted 2-sum problem

            l,r = 0,len(nums)-1

            while l < r:

                s = nums[l] + nums[r]

                if s == target:

                    results.append(result + [nums[l], nums[r]])

                    l += 1

                    while l < r and nums[l] == nums[l-1]:

                        l += 1

                elif s < target:

                    l += 1

                else:

                    r -= 1

        else: # recursively reduce N

            for i in range(len(nums)-N+1):

                if i == 0 or (i > 0 and nums[i-1] != nums[i]):

                    findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)

    results = []

    findNsum(sorted(nums), target, 4, [], results)

    return results

第一个if为初始条件判断。

第二个if判断是否为叶结点，且是否满足条件

else后面是对于非叶结点

秒客网