回溯算法基础

概念

回溯算法（Backtracking Algorithm）是一种用于解决在搜索问题中找到所有可能解的常用算法。回溯算法的核心思想是逐步构建问题的解决方案，并在发现当前解决方案无法满足问题要求时，回溯到上一个步骤，尝试不同的选择，直到找到所有可能的解或确定无解。这一过程可以看作是在一个决策树或状态树上的深度优先搜索。

回溯法可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个岔路口的去尝试找到目的地。如果走错了路，继续返回来找到岔路口的另一条路，直到找到目的地。

回溯算法通常涉及以下步骤：

选择一个候选解的初始状态。
逐步构建解决方案，每一步都尝试一个可能的选择。
检查当前选择是否满足问题的要求。如果满足，继续下一步；如果不满足，回溯到上一个步骤，尝试其他选择。
重复步骤2和步骤3，直到找到一个解决方案或确定没有更多的选择。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

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

回溯算法模版

摘录自代码随想录-回溯法模版
回溯函数伪代码如下：

def backtracking(路径,选择列表):

回溯函数终止条件
既然是树形结构，遍历树形结构一定要有终止条件,所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：

if 终止条件:
	存放结果
	return

回溯搜索的遍历过程
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：

for 选择 in 本层选择列表:
	处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：

def backtracking(路径,选择列表):
	if 终止条件:
		存放结果
		return   
	for 选择 in 本层选择列表:
		做选择
	    backtracking(路径，选择列表) # 递归
	    回溯，撤销选择

例题

组合

77. 组合 - 力扣（LeetCode）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入： n = 4, k = 2
输出：

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入： n = 1, k = 1
输出： [[1]]
提示：

1 <= n <= 20
1 <= k <= n

回溯代码

class Solution:
    def __init__(self):
        self.tmp = []
        self.res =[]
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.getlist(n,1,k)
        return self.res
    # 回溯函数
    def getlist(self, n, index, k):
        if len(self.tmp)==k:
            self.res.append(self.tmp[:]) # 存放结果，注意这里必须为tmp[:]，不然tmp内容改变后res中的内容也会随着改变
            return
        
        for i in range(index,n+1):
            self.tmp.append(i)     # 处理节点
            self.getlist(n,i+1,k)  # 递归函数
            self.tmp.pop()         # 回溯，撤销处理结果

组合总和2

40. 组合总和 II - 力扣（LeetCode）

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:

[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:

[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

解题

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        res =[]
        self.getNum(candidates,target,0,[],res)
        return res

    def getNum(self,candidates,target,start,tmp,res):
        # print(start)
        if target<0:
            return
        if target==0:
            res.append(tmp[:])
            return
        for i in range(start,len(candidates)):
            # 如果当前值大于目标值，便不再继续
            if candidates[i]>target:
                break
            # 如果有重复数字，那么就跳过，注意，是从start位置开始判断
            if i>start and candidates[i]==candidates[i-1]:
                continue
            tmp.append(candidates[i])
            # 每次让 target-当前值
            self.getNum(candidates,target-candidates[i],i+1,tmp,res) # 递归算法
            tmp.pop()                                                # 回溯