回溯

回溯算法

1. 回溯法是一种回溯搜索法,它是一种搜索方法。

2. 回溯伴随着递归,只要有递归就会有回溯。

3. 回溯并不是什么高效算法,是暴力搜索+剪枝

4. 回溯法在某些情况下会超时,如果超时改用DP

回溯算法解决的问题

• 组合问题: N个数里面按一定规则找出k个数的集合。
• 切割问题: 一个字符串案一定规则有几种切割方式。
• 子集问题: 一个N个数的集合里有多少符合条件的子集。
• 排列问题: N个数按一定规则全排列,有几种排列方式。
• 棋盘问题: N皇后,解数独等等。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集,

集合大小构成树的宽度,递归深度构成树的深度。

递归就要有终止条件,所以必然是一颗高度有限的树(N叉树)

回溯三部曲

1. 定参数和返回值
2. 定终止条件
3. 单次循环遍历过程

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

力扣案列 - 组合问题

1. leetcode77. 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。

输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

• 确定dfs参数 我们需要n,k 以及index索引

  
dfs(n int, k int, startIndex int)

• 确定终止条件 当每个[]int的长度=k时,将其拷贝并添加到返回结果中

if len(arr) == k {
        tmp := make([]int,k)
        copy(tmp,arr)
        res = append(res, tmp)
        return 
    }

• 确定单次循环遍历操作 先append,再循环dfs到第二层,再append,等长度以满 回溯

  for i := startIndex; i <= n - (k - len(arr))+1;i++ {
        arr = append(arr, i)
        dfs(n,k,i+1)
        arr = arr[:len(arr)-1]
    }

2. leetcode 216. 组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 返回 所有可能的有效组合的列表。 该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。

思路

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。

相对于77. 组合 (opens new window)，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,...,9]。

想到这一点了，做过77. 组合 (opens new window)之后，本题是简单一些了。

本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。

例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。

• 确定dfs参数 我们需要n,k 以及index索引

  
dfs(k, n int, start int, sum int)

• 确定终止条件 当每个[]int的长度=k sum=n时,将其拷贝并添加到返回结果中

if len(arr) == k {
        if sum == n {
            tmp := make([]int, k)
            copy(tmp, path)
            res = append(res, tmp)
        }
        return 
    }

• 确定单次循环遍历操作

  for i := index; i <= 9; i++ {
        if sum + i > n  {
            break
        }
        path = append(path, i)
        dfs(k, n, i+1, sum+i)
        path = path[:len(path)-1]
    }

3. leetcode17 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路:

1. 建立字符串和数字映射因为2-9 []string{} 
2. 遍历数字对应的字母,初始化index为0 为第一层,index等于树高可以返回叶子节点 
3. 存储并返回数组

• 确定dfs参数 我们需要index索引控制层数

  
dfs(digists string,index int)

• 确定终止条件 当每个[]int的长度=k时,将其拷贝并添加到返回结果中

if len(path) == len(digits) {  //终止条件，字符串长度等于digits的长度
        tmp := string(path)
        res = append(res, tmp)
        return
    }

• 确定单次循环遍历操作

 digit := int(digits[start] - '0')  // 将index指向的数字转为int（确定下一个数字）
    str := m[digit]   // 取数字对应的字符集（注意和map中的对应）
    for j := 0; j < len(str); j++ {
    path = append(path, str[j])
    dfs(digits, start+1)
    path = path[:len(path)-1]
    }