敲响警钟之回溯算法真的很重要ballball了看看他
首先要明白所谓的回溯算法其实本质上就是递归的衍生，其实就是dfs
看一下回溯算法的模板
void backtracking(参数待定){
if(设置终止条件){
//设置所谓的终止条件，就是设置一个条件，当判断已经到达叶子结点之后应该进行如何的操作.
xx.add();
return;
}
for(){
//这个for也是经典，会在这里遍历剩余集合的节点，有什么节点我们可以看着来
}
}
切记，一整个回溯的算法，或者叫dfs算法，更像是一颗数的结构。在对于树做一个暴力遍历，求出每一种情况，然后进行求解。
77.组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
- 说明了返回的值是K个数的组合。那么所谓终止的条件，就是所谓的叶子结点，它的条件就是这个组合的长度达到了K。
- 这个是组合，并不是排序。所以我们开始规定不能有重复元素
class Solution {
List<Integer> path = new LinkedList();//定义路径长度
List<List<Integer>> res = new LinkedList();//设定返回值
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return res;
}
public void backtracking(int n,int k,int startindex){
if(path.size() == k){
//终止条件就是Path的路径长度，其实在这用startindex就去重了，但是对于去重的这个理念我理解的还是不太ok
res.add(new LinkedList(path));
return;
}
//对于迭代循环
for(int i = startindex;i<=n;i++){
path.add(i);
backtracking(n,k,i+1);
path.remove(path.size()-1);
}
}
}
一个基础的回溯算法写好了
这个时候我们假设一种情况也就是 n=4 k=4的时候。这个时候明显只有一种排列情况也就是[1,2,3,4]
核心点是，你后期的元素不够支撑。比如第一次取3，后面还能取1，但是需要的元素是3个，只能有两个元素给你用，当然不够。在这个地方就能进行剪枝
if((n-startindex+1) < k-path.size()) return;
综上，加入这一条语句。
17 电话号码的组合方式
这题还算简单pass
40 组合总数2
这题的大体思路还是相同的，但是在去重这一点很重要。这题的去重思路真的，一开始我的脑子里只有，先把结果查出来，然后对于结果去重这一个思路。
但是现在给出的思路是，纵向的代表同一个组合中的元素，横向的代表的是不同组合中的元素。纵向的是可以重复的，而横向的是不可以的。
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length==0) return res;
Arrays.sort(candidates);
visited = new boolean[candidates.length];
backtracking(candidates,target,0);
return res;
}
public void backtracking(int[] candidates,int target,int startindex){
if(sum == target){
//设置终止条件，相等的情况
res.add(new LinkedList(path));
return;
}else if(sum > target) return;
for(int i = startindex;i<candidates.length;i++){
if(i>0 && candidates[i] == candidates[i-1] && !visited[i-1]) continue;
visited[i] = true;
sum += candidates[i];
path.add(candidates[i]);
backtracking(candidates,target,i+1);
sum -= candidates[i];
path.remove(path.size()-1);
visited[i] = false;
}
}
39 组合总和
这道题很有意思，第一次做的时候做出来了，第二次做反而卡克了。
有一点在第一次没考虑竟然误打误撞做出来了。那就是对于相同元素的把握这个和分割的题目是一个道理。我一直在考虑怎么分割，怎么去做这个事情。其实情况已经包含了,我不知道如何去形容这种感觉很神奇自己体悟。
int sum = 0;
List<Integer> path = new LinkedList();
List<List<Integer>> res = new LinkedList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates == null || candidates.length == 0) return res;
backtracking(candidates,target,0);
return res;
}
public void backtracking(int[] candidates,int target,int startindex){
if(sum == target){
//设置终止条件，终止条件就是sum=target呗
res.add(new ArrayList(path));
return;
}else if(sum > target) return;
for(int i = startindex;i<candidates.length;i++){
sum += candidates[i];
path.add(candidates[i]);
backtracking(candidates,target,i);
sum -= candidates[i];
path.remove(path.size()-1);
}
}
40 组合3
这题的核心在于去重，这个回溯算法也是分为横向和纵向的。横向的表示这一层的节点，纵向的表示同一个排列中的节点。排完序后，你去去重就是同一层的节点不能使用第二次，看看代码中是如何保证的，十分精妙。
int sum = 0;
List<Integer> path = new LinkedList(); //记录路径
List<List<Integer>> res = new LinkedList(); //返回值
boolean[] visited;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
visited = new boolean[candidates.length];
Arrays.sort(candidates);
backtracking(candidates,target,0);
return res;
}
public void backtracking(int[] candidates,int target,int startindex){
if(sum == target){
res.add(new LinkedList(path));
return;
}else if(sum > target) return;
for(int i = startindex;i<candidates.length;i++){
if(i>0 && candidates[i]== candidates[i-1]){
if(!visited[i-1]) continue;
}
visited[i] = true;
sum += candidates[i];
path.add(candidates[i]);
backtracking(candidates,target,i+1);
sum -= candidates[i];
path.remove(path.size()-1);
visited[i] = false;
}
}
46全排列
这个全排列的题目提醒了我两点
- visited[] 数组的用处是非常大的
- 如果每一次进入递归需要用到整个数组的时候，这个情况是不需要要startindex这个参数的
List<List<Integer>> res = new LinkedList();
List<Integer> path = new LinkedList();
boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
visited = new boolean[nums.length];
backtracking(nums);
return res;
}
public void backtracking(int[] nums){
if(path.size() == nums.length){
res.add(new LinkedList(path));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i]) continue;
visited[i] = true;
path.add(nums[i]);
backtracking(nums);
visited[i] = false;
path.remove(path.size()-1);
}
}