理論
與遞歸相輔相成，遞歸下面的邏輯就是回溯
- 本質：純暴力搜索。
-
回溯算法能解決的問題：（普通for循環(huán)搜不出來）
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
};
剪枝優(yōu)化
思路：如果for循環(huán)選擇的起始位置之后的元素個數(shù) 已經(jīng)不足 我們需要的元素個數(shù)了昵时，那么就沒有必要搜索了
參數(shù)：
image.png
image.png
優(yōu)化過程：
image.png
組合總和 III
-
思路：
image.png
代碼：
var combinationSum3 = function(k, n) {
let sum=0;
let path=[]//控制只有k個數(shù)
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
};
- 剪枝優(yōu)化
思路：sum超過n時捷雕，不繼續(xù)往下搜索
電話號碼的字母組合
- 思路：
回溯三部曲：
- 確定回溯函數(shù)參數(shù)
index: 記錄遍歷第幾個數(shù)字了，就是用來遍歷digits的（題目中給出數(shù)字字符串）壹甥，同時也表示樹的深度救巷。 - 確定終止條件
index 超過digits的大小
-單層遍歷邏輯
此外注意：數(shù)字和字母如何映射
image.png
var letterCombinations = function(digits) {
if(!digits) return []
let res =[]
let path=[]
let map =['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']//用數(shù)據(jù)存儲數(shù)字與字母的映射
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
力扣題目鏈接
與前面題區(qū)別：有重復元素
思路： 使用過的元素僻族，不再使用
樹層去重 樹枝去重
關鍵點：排序
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
};
分割回文子串
思路：
回溯三部曲：
- 參數(shù)：
全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結果集述么。 （這兩個參數(shù)可以放到函數(shù)參數(shù)里）
本題遞歸函數(shù)參數(shù)還需要startIndex蝌数，因為切割過的地方，不能重復切割碉输，和組合問題也是保持一致的籽前。
- 遞歸函數(shù)終止條件
切割線切到了字符串最后面，說明找到了一種切割方法 - 單層搜索的邏輯
在for (int i = startIndex; i < s.size(); i++)循環(huán)中，我們 定義了起始位置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
};
