力扣整理版八：回溯算法（待更新）

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。

组合/切割/子集/排列/棋盘

1、回溯函数返回值和参数：一般为void

2、终止条件：一般到叶子节点终止

3、回溯的遍历过程：集合的大小树的宽度，递归的深度构成树的深度。

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

------------------------------------

(1) 77 组合

(2) 216 组合总和3

(3) 17 电话号码的字母组合

(4) 39 组合总和

(5) 40 组合总和2

(6) 131 分割回文串

(7) 93 复原IP地址

(8) 78 子集

(9) 90 子集2

------------------------------------

一、组合

1、77 组合

77. 组合 - 力扣（LeetCode）

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

------------  python  -------------

未剪枝优化

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:result = []  # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) == k:result.append(path[:])returnfor i in range(startIndex, n + 1):  # 需要优化的地方path.append(i)  # 处理节点self.backtracking(n, k, i + 1, path, result)path.pop()  # 回溯，撤销处理的节点

剪枝优化

class Solution:def backtracing(self,n,k,index,path,result):if len(path)==k:result.append(path[:]) # 这里要[:]拷贝当前路径（切片操作），不然后面的操作会更改path path最后输出的都会是[]# result.append(path)是对path的引用，path.pop()会改变结果returnfor i in range(index,n-(k-len(path))+2):path.append(i)self.backtracing(n,k,i+1,path,result)path.pop()def combine(self, n: int, k: int) -> List[List[int]]:result=[]self.backtracing(n,k,1,[],result)return result

2、216 组合总和3

216. 组合总和 III - 力扣（LeetCode）

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

------------  python  -------------

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []  # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum > targetSum:  # 剪枝操作return  # 如果path的长度等于k但currentSum不等于targetSum，则直接返回if len(path) == k:if currentSum == targetSum:result.append(path[:])returnfor i in range(startIndex, 9 - (k - len(path)) + 2):  # 剪枝currentSum += i  # 处理path.append(i)  # 处理self.backtracking(targetSum, k, currentSum, i + 1, path, result)  # 注意i+1调整startIndexcurrentSum -= i  # 回溯path.pop()  # 回溯

3、17 电话号码的字母组合 

17. 电话号码的字母组合 - 力扣（LeetCode）

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

Tips：对于组合问题如果是一个集合求组合，就需要startindex，如果是多个集合取组合，就不用startindex。

------------  python  -------------

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return list()#如果 digits(s) 是一个空列表 []，那么 ''.join(digits) 会返回一个 空字符串 ""。s=[]result=[]phoneMap = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz",}def backtracing(index):if index==len(digits):result.append("".join(s))returndigit=digits[index]for i in phoneMap[digit]:# s+=i python中字符串不可以修改，但是列表可以pop()s.append(i)backtracing(index+1)s.pop()backtracing(0)return result

4、39 组合总和

39. 组合总和 - 力扣（LeetCode）

题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

------------  python  -------------

未剪枝

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result=[]def backtracing(candidates,target,total,startindex,path,result):if total>target:returnif total==target:result.append(path[:])returnfor i in range(startindex,len(candidates)):total+=candidates[i]path.append(candidates[i])backtracing(candidates,target,total,i,path,result)total-=candidates[i]path.pop()backtracing(candidates,target,0,0,[],result)return resultreturn result

剪枝后

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result=[]def backtracing(candidates,target,total,startindex,path,result):if total==target:result.append(path[:])return# 如果 sum + candidates[i] > target 就终止遍历for i in range(startindex,len(candidates)):if total+candidates[i]>target:break #剪枝total+=candidates[i]path.append(candidates[i])backtracing(candidates,target,total,i,path,result)total-=candidates[i]path.pop()candidates.sort() #需要排序backtracing(candidates,target,0,0,[],result)return result

5、40 组合总和2

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

题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

------------  python  -------------

class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if i > startIndex and candidates[i] == candidates[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i + 1, path, result)total -= candidates[i]path.pop()def combinationSum2(self, candidates, target):result = []candidates.sort()self.backtracking(candidates, target, 0, 0, [], result)return result

二、切割

1、131 分割回文串

131. 分割回文串 - 力扣（LeetCode）

题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

------------  python  -------------

回溯＋高效判断回文子串

class Solution:def partition(self, s: str) -> List[List[str]]:n=len(s)f=[[True]*n for _ in range(n)] #初始化判断矩阵#f[i][j]表示子串s[i:j+1]是否为回文for i in range(n-1,-1,-1): #倒序计算，在i时，i+1计算好了for j in range(i+1,n):f[i][j]=(s[i]==s[j]) and f[i+1][j-1]ans=list()ret=list()def backtracing(startindex):  #startindex:分割线if startindex==n:ret.append(ans[:])returnfor i in range(startindex,n):if f[startindex][i]:ans.append(s[startindex:i+1])backtracing(i+1)ans.pop()backtracing(0)return ret

2、93 复原IP地址

93. 复原 IP 地址 - 力扣（LeetCode）

题目描述：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

------------  python  -------------

class Solution:# 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法def is_valid(self,s,start,end):# if start>end:#     return False   去掉也可以if s[start]=='0' and start!=end:return Falsenum=int(s[start:end+1])return 0<=num<=255def restoreIpAddresses(self, s: str) -> List[str]:res=list()def backtracing(index,path):# 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案if index==len(s) and len(path)==4:res.append('.'.join(path))returnif len(path)>4:return #剪枝for i in range(index,min(index+3,len(s))):if self.is_valid(s,index,i):sub=s[index:i+1]path.append(sub)backtracing(i+1,path)path.pop()backtracing(0,[])return res

三、子集

子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

1、78 子集

78. 子集 - 力扣（LeetCode）

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

------------  python  -------------

class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集，要放在终止添加的上面，否则会漏掉自己# if startIndex >= len(nums):  # 终止条件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

2、90 子集2

90. 子集 II - 力扣（LeetCode）

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

------------  python  -------------

class Solution:def subsetsWithDup(self, nums):result = []path = []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# 而我们要对同一树层使用过的元素进行跳过if i > startIndex and nums[i] == nums[i - 1]:continuepath.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

3、491 非递增子序列 

491. 非递减子序列 - 力扣（LeetCode）

题目描述：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。