0、基础

什么是回溯？

回溯是一种穷举的搜索算法，并不是一个高效的算法，当一些问题暴力搜素也无法穷举的时候就要使用回溯。

回溯法解决的问题都可以抽象为树形结构

回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

本质上是for循环+递归

回溯法解决的问题

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

回溯模板

void backtracking(参数) {if (终止条件) { // 搜索到了叶子结点存放结果; // 子集、某种排列方式、某种切割方式return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

1、组合问题

77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

from  typing import  List
class Solution:def __init__(self):self.path = [] # 存放路径self.result = [] # 存放符合条件（k个数）的结果的二维数组def backtracking(self, n, k, startindex): # 参数n:树的宽度、参数k：遍历的深度、startindex：记录本层递归中集合从哪里开始遍历# 终止条件：到达递归深度：叶子节点：path已经收集到了k个元素if len(self.path) == k:self.result.append(self.path[:])return# 单层逻辑：for从starindex开始遍历，将结果加入path中，然后递归下一层，一直到找到叶子节点，然后返回答案，并撤销处理过程for i in range(startindex, n+1):self.path.append(i)self.backtracking(n, k, i+1)self.path.pop()# 正常情况每一层[i,n]# 但是要考虑到剩余元素不满足k的情况,n = 4 ,k = 4 ,i = 2, 剩余元素个数为n-i+1 = 3,现在记录的个数为len(path)# n - i +1 + len(path)>= k  -> i <= n - k + 1 +len(path)# i \in [startindex,n - k + 1 +len(path)]for i in range(startindex, n - (k - len(self.path)) + 2):self.path.append(i) self.backtracking(n,k,i+1)self.path.pop()        def combine(self, n: int, k: int) -> List[List[int]]:self.backtracking(n, k, 1)return self.result

🌟在for i in range(startindex, n+1):这里面的startindex保证的是树层去重（防止出现[1,2]和[2,1]的情况，组合问题特性 ）
🌟在 self.backtracking(n, k, i+1)：这里面的i+1保证的是树枝去重（防止出现[1,1]的情况，也就是同一个元素取了两次，这是一个元素只能出现一次的特性 ）

😙剪枝优化：当目前剩余可以选择的元素不够k的时候就没必要继续了，n - i +1 + len(path)>= k -> i <= n - k + 1 +len(path)

❤️为什么是path[:]不是path？

• 浅拷贝vs引用
• path[:] 是浅拷贝，之后对 self.path 的修改不会影响已经存储在 self.res 中的结果
• path是引用，如果 self.path 在之后的递归中被修改，那么 self.res 中的结果也会被修改，因为它们指向的是同一个列表对象。

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。
  

class Solution:def __init__(self):self.res = []self.path = []def backtracking(self, n , k, sum, startindex):# 剪枝：当前sum已经超过n的节点就不需要继续遍历了if sum > n:return# 终止条件：path的长度为kif len(self.path) == k:if sum == n: # 如果此时计算的path路径上的值的和为n，就是一种结果组合self.res.append(self.path[:])return# for循环横向遍历，不能有重复的数for i in range(startindex, 10):sum += iself.path.append(i)self.backtracking(n, k, sum, i+1)sum -= iself.path.pop()def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.backtracking(n,k,0,1)return self.res

🌟组合问题：for i in range(startindex,n)
🌟无重复元素：backtracking(n,k,i+1)
😙剪枝优化：
1️⃣ 当前总和已经超过n：if sum > n:
2️⃣ 当前剩余元素的数量加上已经记录的元素数量要保证超过k个：9-i+1 + len(path) >=k ➡️ i<=9 - (k - path.size()) + 1

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

class Solution:def __init__(self):self.s = ""self.result = []self.lettermap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]def backtracking(self, digits, index):if index == len(digits):self.result.append(self.s)return# 把当前处理的字符“2”变成数字2digit = int(digits[index])stringletter = self.lettermap[digit]for letter in stringletter:self.s += letterself.backtracking(digits, index + 1)self.s = self.s[:-1]def letterCombinations(self, digits: str) -> List[str]:if not digits:return []self.backtracking(digits, 0)return self.result

39. 组合总和：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

class Solution:def __init__(self):self.path = []self.res = []self.sum = 0def backtracking(self,candidates,target,startindex):if self.sum > target:returnif self.sum == target:self.res.append(self.path[:])return for i in range(startindex,len(candidates)):self.sum += candidates[i]self.path.append(candidates[i])self.backtracking(candidates,target,i)self.sum -= candidates[i]self.path.pop()def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.backtracking(candidates,target,0)return self.res

🌟组合问题：for i in range(startindex,n)
🌟可以重复元素：backtracking(n,k,i)

40.组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

🔴数组中含有重复元素
🔴每个元素只能用一次➡️组合中同一元素不能重复
🔴组合问题

class Solution:def backtracking(self, candidates, target, total, startIndex, used, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):# 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])used[i] = Trueself.backtracking(candidates, target, total, i + 1, used, path, result)used[i] = Falsetotal -= candidates[i]path.pop()def combinationSum2(self, candidates, target):used = [False] * len(candidates)result = []candidates.sort()self.backtracking(candidates, target, 0, 0, used, [], result)return result

🌟组合问题：for i in range(startindex,n)
🌟无重复元素：backtracking(n,k,i+1)
☀️因为初始数组[1,1,2,3]存在重复元素，有可能出现这样的情况，[1(0),2,3]和[1(1),2,3]、虽然满足无重复元素（原数组的不同元素），但是生成的新组合还是重复了，so，需要删除这种重复
if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == false: