理论
与递归相辅相成，递归下面的逻辑就是回溯
- 本质：纯暴力搜索。
-
回溯算法能解决的问题：（普通for循环搜不出来）
image.png
排列和组合的差别：
组合没有顺序，排列有顺序
理解时，用图形化的理解：抽象为树形结构。
解题模版：
image.png
77.组合
leecode题目
图示：
image.png
var combine = function(n, k) {
let path=[]
let res=[]
let arr=[]
for(let i =1;i<=n;i++){
arr[i-1]=i
}
var backTracking=function(arr,index){
if(path.length ===k){
res.push([...path])
return
}
for(let i=index;i<arr.length;i++){
path.push(arr[i])
backTracking(arr,i+1)
path.pop()
}
}
backTracking(arr,0)
return res
};
剪枝优化
思路：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了
参数：
image.png
image.png
优化过程：
image.png
组合总和 III
-
思路：
image.png
代码：
var combinationSum3 = function(k, n) {
let sum=0;
let path=[]//控制只有k个数
let res= []
let arr=[1,2,3,4,5,6,7,8,9]
var backTracking =function(n,k,sum,startIndex){
if(path.length===k){
if(sum === n){
res.push([...path])
}
return
}
for(let i=startIndex;i<arr.length;i++){
sum +=arr[i]
path.push(arr[i])
backTracking(n,k,sum,i+1)
sum -=arr[i]
path.pop()
}
}
backTracking(n,k,sum,0)
return res
};
- 剪枝优化
思路：sum超过n时，不继续往下搜索
电话号码的字母组合
- 思路：
回溯三部曲：
- 确定回溯函数参数
index: 记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时也表示树的深度。 - 确定终止条件
index 超过digits的大小
-单层遍历逻辑
此外注意：数字和字母如何映射
image.png
var letterCombinations = function(digits) {
if(!digits) return []
let res =[]
let path=[]
let map =['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']//用数据存储数字与字母的映射
var backTracking=function(map,index){
if(index >=digits.length){
res.push(path.join(''))
return
}
let str = map[digits[index]]
for(let i=0;i<str.length;i++){
path.push(str[i])
backTracking(map,index+1)
path.pop()
}
}
backTracking(map,0)
return res
};
组合综合
力扣题目
1.思路：
跟 77.组合不同的地方是，可以选取重复元素
image.png
拓展：
对于组合问题，什么时候需要startIndex呢？
如果是一个集合来求组合的话，就需要startIndex，例如：77.组合，216.组合总和III 。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合(opens new window)
var combinationSum = function(candidates, target) {
let res =[]
let path=[]
let sum=0
let backTracking=function(sum,index){
if(sum > target){
return
}
if(sum === target){
res.push([...path])
}
for(let i=index;i<candidates.length;i++){
path.push(candidates[i])
sum +=candidates[i]
backTracking(sum,i)
sum -=candidates[i]
path.pop()
}
}
backTracking(sum,0)
return res
};
组合总和2
力扣题目链接
与前面题区别：有重复元素
思路： 使用过的元素，不再使用
树层去重 树枝去重
关键点：排序
image.png
var combinationSum2 = function(candidates, target) {
let res=[]
let path=[]
let sum=0
candidates.sort((a,b)=>a-b);
let used=[]
let backTacking=function(sum,startIndex,used){
if(sum > target) return
if(sum ===target){
res.push([...path])
return
}
for(let i=startIndex;i<candidates.length;i++){
//used[i-1] 为true表示，前一个元素未用过
if(i>startIndex && candidates[i]===candidates[i-1] && !used[i-1]){
continue
}
sum +=candidates[i]
used[i] =true
path.push(candidates[i])
backTacking(sum,i+1,used)
sum -=candidates[i]
path.pop()
used[i] =false
}
}
backTacking(sum,0,used)
return res
};
分割回文子串
思路：
回溯三部曲：
- 参数：
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
- 递归函数终止条件
切割线切到了字符串最后面，说明找到了一种切割方法 - 单层搜索的逻辑
在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。
此外：判断是否是回文子串。
image.png
var partition = function(s) {
let res=[]
let path=[]
var backtracking = function(s,startIndex){
if(startIndex>=s.length){
res.push([...path])
}
for(let i=startIndex;i<s.length;i++){
if(isHuiwen(s.substring(startIndex,i+1))){
path.push(s.substring(startIndex,i+1))
backtracking(s,i+1)
path.pop()
}
}
}
backtracking(s,0)
return res
};
function isHuiwen(str){
for(let i=0,j=str.length-1;i<str.length;i++,j--){
if(str[i] !=str[j]){
return false
}
}
return true
}
复原 IP 地址
leecode题目
思路：
回溯三部曲
- 确定终止条件
path的长度大于等于4 -
单层遍历逻辑
合法的子串放入path
image.png
var restoreIpAddresses = function(s) {
let path=[]
let res=[]
let backTracking=function(startIndex){
const len = path.length;
if(len > 4) return;
if(len === 4 && startIndex === s.length) {
res.push(path.join("."));
return;
}
for(let i=startIndex;i<s.length;i++){
const str = s.slice(startIndex, i + 1);
if(isValid(str)){
path.push(s.slice(startIndex,i+1))
backTracking(i+1)
path.pop()
}
}
}
backTracking(0,0)
return res
};
function isValid(str){
if(str.length > 3 || str > 255) return false;
if(str.length > 1 && str[0] === "0") return false;
return true
}
子集
力扣题目
思路：
image.png
var subsets = function(nums) {
let res = []
let path=[]
let backTracking=function(startIndex){
res.push([...path])
if(startIndex>=nums.length)return
for(let i=startIndex;i<nums.length;i++){
path.push(nums[i])
backTracking(i+1)
path.pop()
}
}
backTracking(0)
return res
};
