回溯的过程就是构建二叉树的过程，通过添加判断项，在构建二叉树的过程中进行剪枝，可以有效的提升运算速度。很多题目，如果用Python写，不添加剪枝策略，时间复杂度就会很高。

回溯算法基础概念

基本理解

递归、深度优先搜索、回溯算法、动态规划的相互关系？

\[ Recursion \subseteq DFS(Option: BackTrack) \subseteq Dynamic\ Programming \]

• 递归是DFS（深度优先搜索）的一种实现方式，递归也可以实现分治思想（归并排序）。

• DFS是动态规划的一种实现方式。

• 回溯法是DFS过程中可以进行的可选操作，也可以认为是一种固定的套路/模板。

如何可视化回溯算？

通过构建二叉树，可以可视化回溯过程。回溯的过程就是构建二叉树的过程，通过添加判断项，在构建二叉树的过程中进行剪枝，可以有效的提升运算速度。

画二叉树，回溯的过程就是构建二叉树的过程，通过添加判断项，在构建二叉树的过程中进行剪枝，可以有效的提升运算速度。

用这种套路有什么好处呢？

利用回溯算法，利用将解空间缩小。

如何判断是否应该使用回溯算法？

当要解决的问题涉及过程选择、条件控制，解空间特别大的时候，比如下棋、路径规划、排列、组合、字符串匹配等问题，都可以考虑用回溯算法解决。

回溯算法的三个关键点

解决一个回溯问题，实际上就是一个决策树的遍历过程，你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。(Our Choice) 2、选择列表：也就是你当前可以做的选择。（Our Constraints） 3、结束条件：也就是到达决策树底层，无法再做选择的条件。（Our Goal）

回溯算法的框架

result = []
def backtrack(路径, 选择列表): 
    if 满足结束条件:
        result.add(路径)  # 路径就是要添加的结果
        return           # 大多数情况下，有return会运行快一点。

    for 选择 in 选择列表: # 选择列表是由一系列参数组成的
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

所谓模板、框架，只是给我们一个启示，但是千万别过度依赖算法模板、框架，理解算法思想的精髓才是关键，我就因为过渡相信模板、框架，错失了一道本应该能做对的题，详情。

回溯算法思维导图

6a464ba95a7ad1c247aa39610535984c241e6b95148f8bc36b02908a190b1d54-image.png

思路步骤

第 1 步都是先画图，画图是非常重要的，只有画图才能帮助我们想清楚递归结构，想清楚如何剪枝。就拿题目中的示例，想一想人手动操作是怎么做的，一般这样下来，这棵递归树都不难画出。

即在画图的过程中思考清楚： 1、分支如何产生； 2、题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？ 3、哪些搜索是会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？

剪枝！剪枝！剪枝！

由于回溯算法的时间复杂度很高，因此，如果在遍历的时候，如果能够提前知道这一条分支不能搜索到满意的结果，就可以提前结束，这一步操作称之为剪枝。

回溯算法会大量应用“剪枝”技巧达到以加快搜索速度。有些时候，需要做一些预处理工作（例如排序）才能达到剪枝的目的。预处理工作虽然也消耗时间，但一般而且能够剪枝节约的时间更多。还有正是因为回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。否则时间消耗又上去了。

没有剪枝的回溯算法不是合格的回溯算法。

去重和剪枝的区别

去重是把答案中重复的部分去掉，剪枝是结合题意，缩小选择空间，减少不必要的选择，在结束条件之后加 return 就是一种剪枝。

参考连接

LeetCode 大佬题解

回溯算法基础代码

排列组合的定义

排列，排列的定义是指从 \(n\) 个不同元素中，任取 \(m\) ( \(m≤n\), \(m\) 与 \(n\) 均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个排列；从 \(n\) 个不同元素中取出 \(m\) (\(m≤n\)）个元素的所有排列的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的排列数。排列本质就是有序组合，计算公式如下 \[ A_n^m = n \times (n-1) \times ...... \times (n-m+1) = \frac{n!}{(n-m)!} \] 例如： \[ A_6^4 = \frac{6!}{4!} = \frac{6 \times 5 \times 4 \times 3 \times 2!}{2!} = 6 \times 5 \times 4 \times 3 = 360 \] 组合，组合的定义是指从 \(n\) 个不同元素中，任取 \(m\) (\(m≤n\)）个元素并成一组，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合；从 \(n\) 个不同元素中取出 \(m\) (\(m≤n\) ）个元素的所有组合的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数。本质就是无序组合，公式如下 \[ C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m! \times (n-m)!} = C_n^{n-m} \] 例如： \[ C_6^4 = \frac{6!}{4! \times (6-4)!} = \frac{6 \times 5 \times 4!}{4! \times 2!} = \frac{6 \times 5}{2!} = 15 \] 注意：规定 \(0! = 1\)。

排列 和 组合 的本质区别在于：决策的顺序对结果有没有影响。

• 九个人，选三个人出来，先后颁发金、银、铜三色奖牌，是一个排列问题。
• 九个人，选三个人出来，先后颁发三瓶可乐，是一个组合问题。

排列

无重复数字

给定一个 没有重复数字 的序列 和 排列元素个数 m，返回其所有可能的排列。written by hand require

以下代码，以行数最短为目标，但是实际运行过程中，建议在终止条件之后加上 return。

额外变量法

14行代码实现全排列回溯算法，基于额外的 bool 数组记录每个元素的使用情况，拿时间换空间是永恒不变的道理。

def permute(nums, m):                           # 1
    """
    :param nums: List[int]
    :param m: int    
    :return: List[List[int]]
    """
    if not nums: return                         # 2
    res = []                                    # 3 注意res要写在backtrack方法上面
    n = len(nums)                               # 4
    visited = [0] * n                           # 5 visited数组记录该元素是否已经被选择

    def backtrack(path, depth):                 # 6
        """backtrack based on extra space visted vector
        :param path: List[int]
        :param depth: int
        :return: None
        """
        # depth是递归的深度也是path的长度
        if depth == m:  res.append(path[:])     # 7
        for i in range(n):                      # 8
            if visited[i]:  continue            # 9
            visited[i] = 1                      # 10
            # path+[nums[i]]这样写更简洁，就不用先append后pop了，也就是先选择，后撤销选择了。
            backtrack(path+[nums[i]], depth+1)  # 11
            visited[i] = 0                      # 12

    backtrack([],0)                             # 13
    return res                                  # 14

注意：正常情况下，回溯算法是按照 选择 递归 撤销选择 的顺序进行执行的。

for i in range(n):                      # 1
    if visited[i]:  continue            # 2
    visited[i] = 1                      # 3 选择
    path.append(nums[i])                # 4 选择
    backtrack(path, depth+1)            # 5 递归回溯
    visited[i] = 0                      # 6 撤销选择
    path.pop()                          # 7 撤销选择

但是，如果选择是往选择路径 path 添加元素，则可以简化成下面这种形式。

for i in range(n):                      # 1
    if visited[i]:  continue            # 2
    visited[i] = 1                      # 3 选择
    backtrack(path+[nums[i]], depth+1)  # 4 递归回溯
    visited[i] = 0                      # 5 撤销选择

挖洞法

10代码实现全排列回溯算法，递归回溯时去掉已经选择的对象，特点结构简单。

def permute(nums, m):                                               # 1
    """
    :param nums: List[int]
    :param m: int   
    :return: List[List[int]]
    """
    if not nums: return                                             # 2
    res = []                                                        # 3
    n = len(nums)                                                   # 4
    
    def backtrack(nums, path, depth):                               # 5
        """backtrack based on the digging out select number
        :param nums: List[int]
        :param path: List[int]
        :param depth: depth
        :return: None
        """
        if depth == m:  res.append(path[:])                          # 6
        # 以range(len(nums))作为选择列表，则之前那个已经被挖掉的元素不会再被选择
        for i in range(len(nums)):                                   # 7
            # 递归调用时就挖掉了那个已经选择的元素
            backtrack(nums[:i]+nums[i+1:], path+[nums[i]], depth+1)  # 8
    
    backtrack(nums, [], 0)                                           # 9
    return res                                                       # 10

交换法

11行代码实现全排列回溯算法，递归回溯时直接在 nums 上操作，将第 i 个整数放在当前排列的待安置位置，特点：不需要 select，理解较为困难。

def permute( nums, m):                                            # 1
    if not nums: return                                           # 2
    res = []                                                      # 3
    n = len(nums)                                                 # 4

    def backtrack(depth=0):                                       # 5
        # 当交换到最后一位的时候，就将此时的解算入解集中，然后返回上层递归。
        if depth == m: res.append(nums[:m])                       # 6
        for i in range(depth, n):                                 # 7
            # 将第i个整数放在当前排列的待安置位置(select[path])。
            nums[depth], nums[i] = nums[i], nums[depth]           # 8
            backtrack(depth + 1)                                  # 9
            # 撤销交换
            nums[depth], nums[i] = nums[i], nums[depth]           # 10

    backtrack()                                                   # 11
    return res                                                    # 12

时间复杂度：\(O(N \times N!)\)，在第 1 层，结点个数为 \(N\) 个数选 1 个的排列，故为 \(A_N^1\) 。在第 2 层，结点个数为 \(N\) 个数选 2 个的排列，故为 \(A_N^2\) 。一共有 \(N\) 层，所以时间复杂度为 =\(O(N \times N!)\)。

空间复杂度：\(O(N×N!)\) ，（1）递归树深度 \(logN\)； （2）全排列个数 \(N!\)，每个全排列占空间 \(N\)。取较大者。

有重复数字

给定一个 可能包含重复数字 的序列 和 排列元素个数 m，返回所有不重复的排列。written by hand require

• 16行代码完成有重复数字的全排列算法问题

在类型1的基础上加上了剪枝策略，不同回溯算法，剪枝策略不一样，这里使用14行代码的版本进行剪枝，应用额外的 bool 数组，记录每个元素的使用情况，所以可以方便的进行剪枝。

剪枝原则：当该节点没有被使用，且该节点和前面节点的数值一样时，这个节点就应该被剪枝跳过。

除了判定前后两个数必须相同以外，还要判定当前位置的前面一个位置（ index - 1 ）是否被占用，因为前一个位置在回溯时肯定是先被释放了占用了的，加入 not visited[i - 1] 条件，这样的剪枝更彻底。

添加了以下两行

# 所以要对 visited[index-1] 处进行检查。
if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:  continue  # 10
# 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
nums.sort()                                                        # 14

推荐这种在运算过程中剪枝的算法，效率更高，详见 剑指offer 面试题38. 字符串的排列（中）中的对比。

def permuteUnique(nums, m):                                                     # 1
    """permutation with repeatable input
    :param nums: List[int]
    :return: List[List[int]]
    """
    if not nums:  return                                                        # 2
    res = []                                                                    # 3
    n = len(nums)                                                               # 4
    visited = [False] * n                                                       # 5

    def backtrack(path, depth):                                                 # 6
        """backtrack based on extra space visted vector
        :param path: List[int]
        :param depth: int
        :return: None
        """
        if depth == m:  res.append(path[:])                                     # 7
        for i in range(n):                                                      # 8
            if visited[i]:  continue                                            # 9
            # 就加了这一句剪枝，那为什么要求visited[index-1]必须为False？
            # 因为一般回溯到这里时，前面visited[index-1]的占用可能没有被撤销。
            # 所以要对 visited[index-1] 处进行检查。
            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:  continue  # 10
            visited[i] = True                                                   # 11
            backtrack(path+[nums[i]], depth+1)                                  # 12
            visited[i] = False                                                  # 13

    # 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
    nums.sort()                                                                 # 14
    backtrack([], 0)  # 86%                                                     # 15
    return res                                                                  # 16

Java版本

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeetCodeTest {

    public static void main(final String[] args) {
        final int m = 3;
        final List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);
        final Solution so = new Solution();
        final List<List<Integer>> res = so.permute(nums, m);
        System.out.println(res);
        System.out.println(res.size());
    }

}


class Solution {

    List<Integer> nums = new ArrayList<>();
    static List<List<Integer>> res = new ArrayList<>();
    List<Boolean> visited = new ArrayList<>();
    int m = 0;

    /**
     * 带重复数字的全排列生成
     * 
    */
    public List<List<Integer>> permute(final List<Integer> nums, final int m) {

        final int n = nums.size();
        if(nums.isEmpty()) 
            return res;

        this.m = m;
        this.nums = nums; 
        for(int i=0; i<n; i++) {
            this.visited.add(false);
        }
        
        Collections.sort(nums);
        final List<Integer> path = new ArrayList<>();
        backtrack(path, 0);

        return this.res;
    }

    public void backtrack(final List<Integer> path, int depth) {
        // 选择终止
        if (depth == m) {
            this.res.add(path);
        }
        for (int i=0; i<nums.size(); i++) {
            // 减枝
            if (visited.get(i)) {
                continue;
            }
            if (i>0 && nums.get(i)==nums.get(i-1) && !visited.get(i-1)) {
                continue;
            }

            // 选择
            visited.set(i, true);
            path.add(nums.get(i));
            depth = depth + 1;

            // 回溯
            backtrack(path, depth);

            // 撤销选择
            visited.set(i, false);
            path.remove(path.size()-1);
            depth = depth - 1;
        }
    }
}

• 10代码实现有重复数字全排列回溯算法，递归回溯时去掉已经选择的对象，特点结构简单。

修改了以下代码

if depth == m:  res.append(path[:])   
==>
if depth == m and path not in res:  res.append(path[:])   

不推荐这种算法，虽然理解简单，但是运行效率较低。

def permuteUnique(nums, m):                                                     # 1
    """permutation with repeatable input
    :param nums: List[int]
    :return: List[List[int]]
    """
    if not nums:  return                                                        # 2
    res = []                                                                    # 3
    n = len(nums)                                                               # 4

    def backtrack2(nums, path, depth):                                          # 5
        """backtrack based on the digging out select number
        :param nums: List[int]
        :param path: List[int]
        :param depth: depth
        :return: None
        """
        if depth == m and path not in res:  res.append(path[:])                 # 6
        for i in range(len(nums)):                                              # 7
            backtrack2(nums[:i]+nums[i+1:], path+[nums[i]], depth+1)            # 8

    # 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
    backtrack2(nums, [], 0)  # 12.83%                                           # 9
    return res                                                                  # 10

组合（子集）

无重复数字

一般组合（一般子集）

给定一个数组 nums (无重复、不一定连续) ，求 k 个子元素组成的所有组合，14行代码实现。 written by hand require

def subset(nums, k):
    def backtrack(start = 0, path = []):
        cur_len = len(path)
        if cur_len == k:
            res.append(path[:])
            return 
        for i in range(start, n - (k - cur_len) + 1):  # 剪枝策略，详见LeetCode 77题
            backtrack(i + 1, path + [nums[i]])
    n = len(nums)
    if k == n:  return [nums]
    if n <= 0 or k <= 0 or k > n:  return [[]]
    res = []
    backtrack()
    return res

时间复杂度 : \(O(k \times C_N^k)\)。
空间复杂度 : \(O(C_N^k)\) ，用于保存全部组合数以输出。

# Input
nums = [1, 100, 50, 36, 99]
k = 2
res = subset(nums, k)
print(res)
print(len(res))  # 5选2 10种情况
# Output
[[1, 36], [1, 50], [1, 99], [1, 100], [36, 50], [36, 99], [36, 100], [50, 99], [50, 100], [99, 100]]
10

全组合（全子集）

给定一个 nums (无重复、不一定连续) ，求所有子集。

回溯算法 11行代码实现

def subsets(nums):
    """calculate all kinds of subsets based on input list
    :param nums: List[int]
    :param k: int
    :return: List[List[int]]
    """
    if not nums: return []
    n = len(nums)
    res = []
    nums.sort()
    def backtrack(idx, n, path):
        res.append(path[:])  # 无需终止条件，一直往res种加回溯结果就行。
        for i in range(idx, n):
            backtrack(i + 1, n, path + [nums[i]])
    backtrack(0, n, [])
    return re

遍历循环 5行代码实现

def subsets(nums):
    """calculate all kinds of subsets based on input list
    :param nums: List[int]
    :param k: int
    :return: List[List[int]]
    """
    res = [[]]
    for num in nums:
        res += [curr + [num] for curr in res]
    return res

时间复杂度：\(O(N \times 2^N)\)，生成所有子集，并复制到输出结果中。 空间复杂度：\(O(N \times 2^N)\)，这是子集的数量。 对于给定的任意元素，它在子集中有两种情况，存在或者不存在（对应二进制中的 0 和 1）。因此，\(N\) 个数字共有 \(2^N\)个子集。

有重复数字

一般组合（一般子集）

给定一个数组 nums (无重复、不一定连续) ，求 k 个子元素组成的所有组合，15行代码实现。 written by hand require

def subsetWithDup(nums, k):
    """calculate subset with k elements based on input list
    :param nums: List[int]
    :param k: int
    :return: List[List[int]]
    """
    def backtrack(start = 0, path = []):
        cur_len = len(path)
        if cur_len == k:
            if path not in res:  # 此处去重有效
                res.append(path[:])
            return 
        for i in range(start, n - (k - cur_len) + 1):  # 剪枝策略，详见LeetCode 77题
            # if i > start and nums[i] == nums[i-1]:  # 此处去重无效
            #     continue
            backtrack(i + 1, path + [nums[i]])
    n = len(nums)
    if k == n:  return [nums]
    if n <= 0 or k <= 0 or k > n:  return [[]]
    res = []
    backtrack()
    return res

全组合（全子集）

给定一个 nums (有重复、不一定连续) ，求所有子集。

def subsetsWithDup(nums):
    """calculate all kinds of subsets based on input list
    :param nums: List[int]
    :param k: int
    :return: List[List[int]]
    """
    if not nums: return []
    res = []
    nums.sort()  # 去重都要做排序

    def traversal():
        """calculate all kinds of subsets based on traversal
        """
        # 循环开始前先对nums进行排序
        output = [[]]
        tmp = []
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:  
                tmp = [curr + [nums[i]] for curr in tmp]
            else:
                tmp = [curr + [nums[i]] for curr in output]
            output += tmp
        return output

    def backtrack(start, n, path):
        """calculate all kinds of subsets based on traversal
        :param start: int
        :param n: int
        :param path: List[int]
        :return: None
        """
        # if path not in res:  # 去重处1(35.29%)
        #     res.append(path[:])
        res.append(path[:])  # 无需终止条件，一直往res种加回溯结果就行。
        for i in range(start, n):
            if i > start and  nums[i] == nums[i - 1]:  # 去重处2(76.81%)
                continue
            backtrack(i + 1, n, path + [nums[i]])

    # 基于回溯的方法
    n = len(nums)
    backtrack(0, n, [])  # 35.29%/76.81%

    # 基于遍历递归的方法
    # res = traversal()  # 76.81%

    return res

关键思想总结

1、回溯算法的精髓是 “终止条件、路径保存、选择列表” ，有些题目非常灵活的使用了回溯的思想，例如LeetCode 17/22等题目，就是利用回溯算法解决一些字符串生成和搜索的问题。 2、一般来说，下棋或者数独问题都是要用约束编程+回溯算法的思想去解决，例如LeetCode 37/51/52。 3、LeetCode 78，典型的把简单问题复杂化了，求幂子集，直接去掉终止条件，一直递归回溯就行。 4、回溯算法中的输入去重问题，注意学习利用 while 条件在运算过程中去重的方法，例如 LeetCode 90。 5、无重复数字求组合：LeetCode 77/78，有重复数字求组合：LeetCode 90。无重复数字求排列：LeetCode 46，有重复数字求组合：LeetCode 47。 6、回溯算法去重，有两种思路，一是在先sort然后在for循环中跳过重复的，二是在加入时判断是否重复。 7、针对具体问题，多挖掘剪枝条件，LeetCode 93。

相关LeetCode题目

LeetCode 10. 正则表达式匹配（难）

直觉

这个题目，挺难的，其结构不是一道正常的递归回溯题目。走的是先匹配当前字符和pattern第一个字符。再分开考虑无限通配符的情况，具体请看代码注释。

关键代码

class Solution(object):
    # 暴力递归
    def isMatch(self, text, pattern):
        # 当pattern为空时执行以下逻辑
        if not pattern:
            # 如果text非空，空pattern无法匹配非空text，应该返回False，而not text就是False。
            # 如果txt为空，空pattern可以匹配空text，应该返回True，而 not text就是True。
            return not text  

        # 当前第一个字符是否匹配，考虑了.作为通配符的情况。首先text必须非空所以有bool(text)的条件，其次pattern[0]需要为.或者和text[0]相等。
        first_match = bool(text) and pattern[0] in {text[0], '.'}  # 这里必须用bool(text)，不能用text，否者无法判断非空。

        # 考虑无限匹配符*的情况
        if len(pattern) >= 2 and pattern[1] == '*':
            # 考虑匹配0次（传入self.isMatch的是text和pattern[:2]，代表当前text不匹配且跳过pattern[0]和patter[1]，及跳过*匹配项。
            # 或者考虑递归匹配1次（也就是考虑多次），传入self.isMatch的是text[1:]和pattern，代表当前text[0]已经算匹配了的，继续考虑*匹配项。
            # 这两种考虑是or关系，因为题干里面说了'*'是指匹配零个或多个前面的那一个元素。）
            return (self.isMatch(text, pattern[2:]) or
                    first_match and self.isMatch(text[1:], pattern))  
         # 非无限匹配符*的情况，简单的把text和pattern都往后调整即可。
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])  

题解

LeetCode-10-正则表达式匹配（难）

LeetCode 17. 电话号码的字母组合（中）

直觉

给出如下回溯函数 backtrack(combination, next_digits) ，它将一个目前已经产生的组合 combination 和接下来准备要输入的数字 next_digits 作为参数。如果没有更多的数字需要被输入，那意味着当前的组合已经产生好了，可以直接添加。如果还有数字需要被输入：遍历下一个数字所对应的所有映射的字母。将当前的字母添加到组合最后，也就是 combination = combination + letter 。

关键代码

def backtrack(combination, next_digits):
    # 如果没有更多的数字需要被输入，那意味着当前的组合已经产生好了，可以直接添加。
    if not next_digits:
        output.append(combination)
    # 如果还有数字需要被输入，遍历下一个数字所对应的所有映射的字母。
    else:
        # phone[next_digits[0]]是数字代表的字母构成的list ['a', 'b', 'c']
        for letter in phone[next_digits[0]]:
            # 在这里添加letter到前面的combination上，将遍历得到的字母添加到组合最后。
            backtrack(combination + letter, next_digits[1:])

题解

LeetCode 17. 电话号码的字母组合（中）

LeetCode 22. 括号生成（中）

直觉

只有在我们知道序列仍然保持有效时才添加 '(' or ')'，我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，从代码形式上就是先放左括号，后放右括号。

关键代码

def backtrack(S = '', left = 0, right = 0):
    if len(S) == 2 * N:  # 结束条件为S的长度已经达到了2N
        ans.append(S)
        return  # 完成一次有效选择，返回上一层
    
    # 开始做选择
    if left < N:  # 如果left<N说明还可以放置开括号，就添加开括号，先添加开括号。 为什么要优先添加开括号，因为现有”(“后有”)“。
        backtrack(S+'(', left+1, right)  # backtrack(路径, 选择列表)
    
    # 添加完开括号之后，撤销选择。
    if right < left:  # 添加闭括号
        backtrack(S+')', left, right+1)  # 在原来S的基础上添加闭括号，相当于上面没有添加开括号，也就是把选择给撤销了。1

题解

LeetCode 22. 括号生成（中）

LeetCode 37. 解数独（难）★

直觉

基本的意思是在放置每个数字时都设置约束。在数独上放置一个数字后立即排除当前行、列和子方块对该数字的使用。这会传播 约束条件 并有利于减少需要考虑组合的个数。这个情况在N皇后问题中也出现过，N皇后问题也考虑了回溯算法。这说明约束编程和回溯算法一般都会复共同出现，约束编程可以视为一种剪枝策略。

关键代码

# 声明三个hash map用来保存存储关系 实现约束编程
rows = [defaultdict(int) for i in range(N)]
columns = [defaultdict(int) for i in range(N)]
boxes = [defaultdict(int) for i in range(N)]

# 定义could_place方法，检测该位置，是否可以放置该数字。
def could_place(d, row, col):

# 定义place_number方法，将数放置到对应位置，并添加rows、columns、boxes约束。
def place_number(d, row, col):
    
# 定义remove_number方法，将某个位置的数据去掉，替换回'.'，同时去掉约束。
def remove_number(d, row, col):

# 定义place_next_numbers方法。进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
def place_next_numbers(row, col):

# 定义backtrack回溯函数
def backtrack(row = 0, col = 0):
    """
    Backtracking
    """
    # if the cell is empty
    if board[row][col] == '.':  # 如果当前位置是空的，也就是'.'，就从1到10，一个一个的填进去试试。
        for d in range(1, 10):   # 选择列表：range(1, 10)
            if could_place(d, row, col):  # 先判断该位置能不能放这个数
                place_number(d, row, col)  # 做选择：如果没有被约束，就将这个数放到这个位置。
                place_next_numbers(row, col)  # 判断是否终止：然后调用place_next_numbers，进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
                if not sudoku_solved:  # 利用sudoku_solved判定数独是否解决
                    remove_number(d, row, col)  # 撤销：选择如果没有解决，就执行撤销操作。
    else:  # 否则调用place_next_numbers方法，检测下一个位置。
        place_next_numbers(row, col) 
    
# 将str的数独输入转化成int类型，并建立约束。
for i in range(N):
    for j in range(N):
        if board[i][j] != '.': 
            d = int(board[i][j])
            place_number(d, i, j)  # 在这里就把每一个已存在数字的约束建立好

# 声明终止条件sudoku_solved为False并调用backtrack()
sudoku_solved = False
backtrack()

题解

LeetCode 37. 解数独（难）

LeetCode 39. 组合总和（中）★

减法回溯：一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取，解集不能包含重复的组合。

直觉

基于减法回溯，从根结点到叶子结点（必须为 0）的路径，就是题目要我们找的一个组合。

• 去重：通过设置下一轮搜索的起点，防止在较深层的结点重复使用之前使用过的值。
• 剪枝：把候选数组排个序，遇到一个较大的数，如果以这个数为起点都搜索不到结果，后面的数就更搜索不到结果了。

关键代码

def combinationSum():
    def backtrack(path, begin, target)
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return

        for index in range(begin, len(nums)):
            residue = target - nums[index]
            if residue < 0:
                break
            backtrack(path+[nums[index]], index, residue)

    res = []
    nums.sort()
    backtrack([], 0, target)

题解

LeetCode 39. 组合总和（中）

LeetCode 40. 组合总和 II（中）

题目

一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

直觉

主要难点有两个：1、一个数字本身不能重复用。2、去掉重复的组合。 先对数组升序排序，重复的元素一定排在一起，到时候做个判断，跳过就好了。 禁止每一个数字出现多次，只能出现一次，所以，在剪枝后面，再加一个重复数字判断就行。

关键代码

for index in range(begin, length):
    # 剪枝判断，如果当前位置的数字大于residue，由于是sort了的，那后面也不用看了，接break掉。这里是剪枝。
    if (sum(path) + candidates[index]) > target:
        break
    # 在这里进行一个判断，过滤掉那些紧随其后一样的数字，这么写就是为了防止不同数字重复解的出现。这里是去重复。
    if index > begin and candidates[index-1] == candidates[index]:
        continue
    # index+1，这么写就是为了防止数字本身重复。
    backtrack(candidates + [index], index+1, path, res, length)  

candidates.sort()
backtrack(candidates, 0, path, res, length)

题解

LeetCode 40. 组合总和 II（中）

LeetCode 46. 全排列（中）

题目

给定一个没有重复数字的序列，返回其所有可能的全排列。

直觉

• 基于额外的 bool 数组记录每个元素的使用情况
• 递归回溯时去掉已经选择的对象
• 递归回溯时直接在 nums 上操作，将第 i 个整数放在当前排列的待安置位置。

关键代码

def backtrack(nums, path, depth):                               # 5
    """backtrack based on the digging out select number
    :param nums: List[int]
    :param path: List[int]
    :param depth: depth
    :return: None
    """
    if depth == n:  res.append(path)                             # 6
    # 以range(len(nums))作为选择列表，则之前那个已经被挖掉的元素不会再被选择
    for i in range(len(nums)):                                   # 7
        # 递归调用时就挖掉了那个已经选择的元素
        backtrack(nums[:i]+nums[i+1:], path+[nums[i]], depth+1)  # 8

题解

LeetCode 46. 全排列（中）

LeetCode 47. 全排列 II（中）

题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。

直觉

剪枝原则：当该节点没有被使用，且该节点和前面节点的数值一样时，这个节点就应该被剪枝跳过。

除了判定前后两个数必须相同以外，还要判定当前位置的前面一个位置（ index - 1 ）是否被占用，因为前一个位置在回溯时肯定是先被释放了占用了的，加入 not visited[i - 1] 条件，这样的剪枝更彻底。

关键代码

# 给定 bool数组 控制回溯
# 所以要对 visited[index-1] 处进行检查。
if i > 0 and nums[i] == nums[i -1] and not visited[i-1]:  continue  # 10
# 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
nums.sort()                                                         # 14

# 直接将选择过的去掉
if depth == n:  res.append(path[:])   
==>
if depth == n and path not in res:  res.append(path[:])   

题解

LeetCode 47. 全排列 II（中）

LeetCode 51. N皇后（难）★

直觉

当在棋盘上放置了几个皇后且不会相互攻击。但是选择的方案不是最优的，因为无法放置下一个皇后。此时我们该怎么做？回溯。意思是回退一步，来改变最后放置皇后的位置并且接着往下放置。如果还是不行，再回溯。

• 一行只可能有一个皇后且一列也只可能有一个皇后。这意味着没有必要再棋盘上考虑所有的方格。只需要按列循环即可。
• 对于所有的主对角线（左上到右下）有 行号 - 列号 = 常数，对于所有的次对角线（右上到左下）有 行号 + 列号 = 常数。

关键代码

# 判断该位置是否可以用于放置皇后
def could_place(row, col)

# 进行选择：将皇后进行放置，并设置列约束和对角线约束。
def place_queen(row, col)

# 撤销选择：解除该位置的占用
def remove_queen(row, col)

# 添加结果：将结果转化为题目要求的形式
def add_solution()

def backtrack(row = 0):
    for col in range(n):  # 选择列表 遍历这一行的所有列 以找到一个位置放入皇后
        if could_place(row, col):
            place_queen(row, col)  # 进行选择
            if row + 1 == n:  # 结束条件
                add_solution()
            else:
                backtrack(row + 1)  # 递归回溯，列不变
            remove_queen(row, col)  # 撤销选择

题解

LeetCode 51. N皇后（难）

LeetCode 52. N皇后 II（难）

直觉

与51题一样，不过返回的不是具体的解答，而是解答的个数。修改部分代码即可，去掉变量 queens 和 out_put 以及函数 add_solution，直接在满足终止条件时，执行 count += 1，返回 count 结果就行。

这一题也可以使用位运算（位图）来实现，不过理解较为复杂。

关键代码

• 传统代码

def could_place(row, col):
    
def place_queen(row, col)

def remove_queen(row, col)

def backtrack(row = 0, count = 0):  # 默认backtrack从第0行开始
    for col in range(n):  # <选择列表> 逐列添加
        if could_place(row, col):  # 判断当前位置是否可以添加皇后
            place_queen(row, col)  # 执行选择
            if row + 1 == n:  # <结束条件> Our Goal 遍历完所有行
                count += 1  # 发现一个解，count加1
            else:
                count = backtrack(row + 1, count)  # 递归回溯， 列不变
            remove_queen(row, col)  # 撤销选择
    return count

• 位运算

class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def backtrack(row = 0, hills = 0, next_row = 0, dales = 0, count = 0):
            """
            :type row: 当前放置皇后的行号
            :type hills: 主对角线占据情况 [1 = 被占据，0 = 未被占据]
            :type next_row: 下一行被占据的情况 [1 = 被占据，0 = 未被占据] 实际上就是记录了还有哪些列可以用
            :type dales: 次对角线占据情况 [1 = 被占据，0 = 未被占据]
            :rtype: 所有可行解的个数
            """
            if row == n:  # 如果已经放置了 n 个皇后
                count += 1  # 累加可行解
            else:
                # 当前行可用的列
                # ! 表示 0 和 1 的含义对于变量 hills, next_row and dales的含义是相反的
                # [1 = 未被占据，0 = 被占据]
                free_columns = columns & ~(hills | next_row | dales)
                # free_columns =  ~(hills | next_row | dales)
                
                # 找到可以放置下一个皇后的列
                while free_columns:
                    # free_columns 的第一个为 '1' 的位在该列我们放置当前皇后
                    curr_column = - free_columns & free_columns
                    # 放置皇后 并且排除对应的列
                    free_columns ^= curr_column
                    count = backtrack(row + 1, 
                                      (hills | curr_column) << 1, 
                                      next_row | curr_column, 
                                      (dales | curr_column) >> 1, 
                                      count)
            return count

        # 棋盘所有的列都可放置，
        # 即，按位表示为 n 个 '1'
        # bin(cols) = 0b1111 (n = 4), bin(cols) = 0b111 (n = 3)
        # [1 = 可放置]
        columns = (1 << n) - 1  # columns中为每一行默认可以放置的位置 全1
        return backtrack()

题解

LeetCode 52. N皇后 II（难）

LeetCode 77. 组合（中）

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

直觉

直接回溯：不设置 is_validate 函数和 used 变量，每次都从下一个位置开始遍历，这样就跳过了重复的情况。

加上剪枝：剪枝要去掉的多余步骤一般出现在循环中，如果已经选了的元素都放到 select 中，一共要选择 k 个元素。那么循环干的事情，是从 [i, n] 这个区间里（注意，左右都是闭区间），找到 k - len(selects)个元素。 i 有一个上限。那这个上限 max(i) 是 n - (k -len(selects)) + 1。所以，我们的剪枝过程就是：把for循环的终止条件从 i < n+1 改成 i < n - (k - len(selects)) + 2。

for i in range(first, n - (k - len(selects)) + 2):
    pre.append(i)
    backtrack(i + 1, selects)
    pre.pop()

也可以用字典序 (二进制排序) 组合来解决，不过理解起来不是很简单。

关键代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(first=1, selects=[]):
            if len(selects) == k:
                res.append(selects[:])
                return
            # for i in range(first, n + 1):  # 剪枝之前 66.70%
            for i in range(first, n - (k - len(selects)) + 2):  # 剪枝之后 97.27%
                selects.append(i)
                backtrack(i+1, selects)
                selects.pop()
        # 特判
        if n <= 0 or k <= 0 or k > n:  return []
        if k == n:  return [list(range(1, n+1))]
        res = []
        backtrack()
        return res

字典序

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 特判
        if n <= 0 or k <= 0 or k > n:  return []
        if k == n:  return [list(range(1, n+1))]
         
        # init first combination
        nums = list(range(1, k + 1)) + [n + 1]
        
        output, j = [], 0
        while j < k:
            # add current combination
            output.append(nums[:k])
            # increase first nums[j] by one
            # if nums[j] + 1 != nums[j + 1]
            j = 0
            while j < k and nums[j + 1] == nums[j] + 1:
                nums[j] = j + 1
                j += 1
            nums[j] += 1
            
        return output

题解

LeetCode 77. 组合（中）

LeetCode 78. 子集（中）

题目

给定一组不含重复元素、也不一定连续的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。

直觉

复杂回溯：回溯产生的是固定长度的组合，这里求解的是所有可能的子集。所以这道题用回溯算法其实挺复杂的，先循环，然后在循环里面回溯。

简单回溯：别把问题想太复杂，既然求的是幂子集，就不用终止条件了，一直递归回溯就成。

遍历递归：这道题实际上可以直接从后遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集。

关键代码

复杂回溯

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first = 0, curr = []):
            if len(curr) == k:  
                output.append(curr[:])
                return
            for i in range(first, n - (k - len(curr)) + 1):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()
        
        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

简单回溯

class Solution:
    def subsets(self,nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        n = len(nums)
        res = []
        nums.sort()

        def backtrack(idx, n, temp_list):
            res.append(temp_list)
            for i in range(idx, n):
                helper1(i + 1, n, temp_list + [nums[i]])

        backtrack(0, n, [])
        return res

遍历递归

def subsets(nums):
    res = [[]]
    for num in nums:
        res += [curr + [num] for curr in res]
    return res

题解

LeetCode 78. 子集（中）

LeetCode 90. 子集 II（中）

题目

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。

直觉

在78题代码的简单回溯、遍历递归两种方法的基础上添加某些限制条件即可。

简单回溯：先将 nums 数组排序，在撤销选择之后，判断后面是否有相同的数字，如果有，就跳过。或者在添加时做个是否重复的判断。

遍历递归：先对 nums 进行排序，判断当前数字和前一个数字是否相似，如果和前一个数字一样，就在前一次循环产生的增量数组 tmp 上添加。如果和前一个数字不一样，就在前一次循环产生的结果 output 上添加。

关键代码

简单回溯

# 思路1
def backtrack1(idx, n, temp_list):
    if temp_list not in res:  # 此处去重
        res.append(temp_list)
    for i in range(idx, n):
        backtrack1(i + 1, n, temp_list + [nums[i]])
# 思路2
def backtrack2(idx, n, temp_list):
    res.append(temp_list)
    for i in range(idx, n):
        if i > idx and  nums[i] == nums[i - 1]:  # 此处去重
            continue
        backtrack2(i + 1, n, temp_list + [nums[i]])

遍历递归

# 循环开始前先对nums进行排序
nums.sort()
tmp = []
for i in range(len(nums)):
    if i > 0 and nums[i - 1] == nums[i]:  
        tmp = [curr + [nums[i]] for curr in tmp]
    else:
        tmp = [curr + [nums[i]] for curr in output]
    output += tmp
return output

题解

LeetCode 90. 子集 II（中）

LeetCode 79. 单词搜索（中）

题目

给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

直觉

以二维数组中每一个数都作为起点和给定字符串做匹配，可以不用 visited 数组，直接对 board 数组进行修改，将其遍历过的位置改为井号，记得递归调用完后需要恢复之前的状态。因为题目要求一个 cell 只能被访问一次。如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等，则对其上下左右四个邻字符分别调用 DFS 的递归函数，只要有一个返回 true，那么就表示可以找到对应的字符串，否则就不能找到。

1、不再是统计path，而是验证结果，返回 True 和 False。 2、不再是单一方向回溯，由于是在矩阵中回溯，所以是四个方向，包括上下左右。

关键代码

class Solution:
    def exist(self, borad, word):
        def backtrack(borad, word, depth, row, col):
            if depth == len(word):  # 终止
                return True
            if row < 0 or col < 0 or row >= rows or col >= cols or borad[row][col] != word[depth]:
                return False
            char = borad[row][col]
            borad[row][col] = "#"  # 选择
            res = backtrack(borad, word, depth+1, row-1, col) or \
                backtrack(borad, word, depth+1, row+1, col) or \
                backtrack(borad, word, depth+1, row, col-1) or \
                backtrack(borad, word, depth+1, row, col+1)  # 回溯
            borad[row][col] = char # 终止
            return res

        if not len(borad) or not len(borad[0]):  return False
        rows = len(borad)
        cols = len(borad[0])
        for row in range(rows):
            for col in range(cols):
                if backtrack(borad, word, 0, row, col):  return True
        return False

题解

LeetCode 79. 单词搜索（中）

LeetCode 89. 格雷编码（中）

题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

直觉

从空字符串开始，一部分分别在末尾加上0、1，下面的另一部分分别在末尾加上1、0，直到长度达n。 所以回溯的终止条件是 len(path) == n，选择列表通过一个 flag 变量判断当前到底是加 0 还是加 1。

关键代码

def backtrack(path, flag):
    if len(path) == n:
        res.append(int(path, 2))
        return
    if flag == 0:  # 上面的（绿色）分别加0、1
        backtrack(path + "0", 0)  # 回溯时顺序不变
        backtrack(path + "1", 1)
    else:  # （红色）分别加1、0
        backtrack(path + "1", 0)  # 回溯时顺序变化
        backtrack(path + "0", 1)

题解

LeetCode 89. 格雷编码（中）

LeetCode 93. 复原IP地址（中）

题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

直觉

IP地址总共有四段，每一段可能有一位，两位或者三位，范围是[字符如果是三位数字且大于255，也需要剪枝。0, 255]。题目明确指出输入字符串只含有数字。 字符如果是三位数字且大于255，也需要剪枝。 截取字符串之后，剩余的字符个数不能过多，过多也需要剪枝。 当只有一位时，0可以成某一段，如果有两位或三位时，像 00， 01， 001， 011， 000等都是不合法的。 终止条件：如果是确定最后一个IP段，那么截取的就应该是全部剩余字符。

关键代码

# 回溯函数
def backtrack(self, s = "", path =  [], depth = 0, res = []):
    if depth == 4:
        res.append(".".join(path))
    else:
        for i in range(1, len(s)+1):
            clip_s = s[:i]
            pruning_result = self.pruning(clip_s, s, i, depth)  # 剪枝
            if pruning_result == 0:
                break
            if pruning_result == -1:
                continue
            path.append(clip_s)  # 选择
            self.backtrack(s[i:], path, depth + 1, res)  # 回溯
            path.pop()  # 撤销选择

# 剪枝函数
def pruning(self, clip_s, s, i, depth):
    if len(clip_s) > 3:  return 0
    if depth == 3 and clip_s != s:  return -1  # continue
    if depth !=3 and len(s[i:]) > (4 - depth - 1) * 3:  return -1  # continue
    if  int(clip_s) > 255:  return -1  # continuereturn -1  # continue
    if len(clip_s) > 1 and clip_s[0] == "0":  return -1  # continue
    return 1  # go on

题解

LeetCode 93. 复原IP地址（中）

LeetCode 95. 不同的二叉搜索树 II（中）

题目

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

直觉

利用回溯法，依次递归回溯构造左右子树。

关键代码

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0: return []
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

题解

LeetCode 95. 不同的二叉搜索树 II（中）