思路:
解决一个回溯问题,实际上就是一个决策树的遍历过程
画出回溯树
- 路径:也就是已经做出的选择。
- 选择列表:也就是你当前可以做的选择。
- 结束条件:也就是到达决策树底层,无法再做选择的条件。
模板:
其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」const result = []
function backtrack(路径, 选择列表){
if (满足结束条件){
result.push(路径)
return
}
for 选择 in 选择列表{
if(已存在/不合法)continue;
做选择
backtrack(路径, 选择列表)
撤销选择
}
}
1.全排列问题
回溯算法的一个特点,不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高
问题:
- 和dfs有点像?
典型题目
1.全排列:1 2 3 4的排列组合
2.N皇后
3.子集:输入一个不包含重复数字的数组,要求算法输出这些数字的所有子集
- 数学归纳思想
回溯算法 ```javascript function subsets(nums){ let result = []; let track = [];
function backtrack(nums,start,track){
result.push(track);
for(let i=0;i<nums.length;i++){
track.push(nums[i]) backtrack(nums,i+1,track); track.pop()
} }
backtrack(nums,0,track);
return result; }
<a name="OxiOO"></a>
#### 4.组合:输入两个数字 `n, k`,算法输出 `[1..n]` 中 k 个数字的所有组合
```javascript
function combine(n,k){
const result = [];
if(k<=0||n>=0)return results;
const track = [];
function backtrack(n,k,start,track){
if(k===track.length){
result.push(track);
return
}
for(let i=start;i<=n;i++){
track.push(i);
backtrack(n,k,i+1,track)
track.pop()
}
}
backtrack(n,k,1,track);
return result;
}
5.排列:不包含重复数字的数组 nums
,返回这些数字的全部排列
function permute(nums){
let results = [],track = [];
function backtrack(nums,track){
if(track.length===nums.length){
results.push(track);
return;
}
for(let i=0;i<nums.length;i++){
if(track.find(t=>t===nums[i])) continue;
track.add(nums[i])
backtrack(nums,track);
track.pop()
}
}
backtrack(nums,track)
return results;
}
6.解数独
7.括号生成
- 合法括号的生成。对于括号合法性的判断,主要是借助「栈」这种数据结构,
括号的生成,一般都要利用回溯递归的思想
function generateParenthesis(n){ let res = [],track=''; function backtrack(left,rigth,track){ if(left<0 || right<0) return;//没有括号了 //1、一个「合法」括号组合的左括号数量一定等于右括号数量,这个很好理解。 //2、对于一个「合法」的括号字符串组合 p,必然对于任何 0 <= i < len(p) 都有:子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。 if(left>right)return; if(left===0&&right===0){ res.push(track); return; } track.push('('); backtrack(left-1,right,track); track.pop(); track.push(')'); backtrack(left,right-1,track); track.pop(); } backtrack(n,n,track) return res; }