十一城

跬步千里,小流江海。

Home Java Python Linux ML Thoughts BookCan Links About

2018-05-08
算法-回溯-基础

• 标签: backtracking

学而不思则罔,思而不学则殆。

本文主体转载自https://blog.csdn.net/versencoder/article/details/52071930 ,进行了修改,并添加了部分内容。

leetcode有一个系列的考察回溯算法,例如Combination Sum 系列 Subsets系列等。

根据百度百科定义:回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

博主在学习回溯算法到应用其完成算法题经历了很多的困惑,查看别人博客的时候基本都是解决某个特定问题,而不是注重方法,相信不少读者看完和我一样一脸懵逼。所以博主想要尝试下写下自己总结的方法。希望这篇博客能够帮助和我一样在学习算法的人!第一次写博客,如有疏漏,欢迎指正。

首先我们来看一道题目:

1
2
3
4
5
6
7
8
9
Combinations:Given two integers n and k,return all possible combinations of k numbersout of 1 ... n. For example, If n = 4 and k =2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

(做一个白话版的描述,给你两个整数 n和k,从1-n中选择k个数字的组合。比如n=4,那么从1,2,3,4中选取两个数字的组合,包括图上所述的四种。)

然后我们看看题目给出的框架:

1
2
3
4
5
public class Solution {
public List<List<Integer>> combine(int n, int k) {
}
}

要求返回的类型是List<List<Integer>> 也就是说将所有可能的组合list(由整数构成)放入另一个list(由list构成)中。

现在进行套路教学:要求返回List<List<Integer>>,那我就给你一个List<List<Integer>>,因此

  1. 定义一个全局的容器List<List<Integer>> result=new ArrayList<List<Integer>>();
  2. 定义一个辅助的方法(函数)public void backtracking(int n,int k, List<Integer>list){}n k 总是要有的吧,加上这两个参数,前面提到List<Integer>是数字的组合,也是需要的吧,这三个是必须的,没问题吧。(可以尝试性地写参数,最后不需要的删除)
  3. 接着就是我们的重头戏了,如何实现这个算法?对于n=4,k=2,1,2,3,4中选2个数字,我们可以做如下尝试,加入先选择1,那我们只需要再选择一个数字,注意这时候k=1了(此时只需要选择1个数字啦)。当然,我们也可以先选择2,3 或者4,通俗化一点,我们可以选择(1-n)的所有数字,这个是可以用一个循环来描述?每次选择一个加入我们的链表list中,下一次只要再选择k-1个数字。那什么时候结束呢?当然是k<0的时候啦,这时候都选完了。

有了上面的分析,我们可以开始填写public void backtracking(int n,int k, List list){}中的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void backtracking(int n,int k,int start,List<Integer> list){
if(k<0) return;
else if(k==0){ //k==0表示已经找到了k个数字的组合,这时候加入全局result中
result.add(new ArrayList(list));
}else{
for(int i=start;i<=n;i++){
list.add(i);//尝试性的加入i
//开始回溯啦,下一次要找的数字减少一个所以用k-1,i+1见后面分析
backtracking(n,k-1,i+1,list);
//(留白,有用=。=)
}
}
}

观察一下上述代码,我们加入了一个start变量,它是i的起点。为什么要加入它呢?比如我们第一次加入了1,下一次搜索的时候还能再搜索1了么?肯定不可以啊!我们必须从他的下一个数字开始,也就是2 、3或者4啦。所以start就是一个开始标记这个很重要啦!

这时候我们在主方法中加入backtracking(n,k,1,list);调试后发现答案不对啊!为什么我的答案比他长那么多?

img

回溯回溯当然要退回再走啦,你不退回,当然又臭又长了!所以我们要在刚才代码注释留白处加上退回语句。仔细分析刚才的过程,我们每次找到了1,2这一对答案以后,下一次希望2退出然后让3进来,1 3就是我们要找的下一个组合。如果不回退,找到了2 ,3又进来,找到了3,4又进来,所以就出现了我们的错误答案。正确的做法就是加上:list.remove(list.size()-1);他的作用就是每次清除一个空位 让后续元素加入。寻找成功,最后一个元素要退位,寻找不到,方法不可行,那么我们回退,也要移除最后一个元素。

所以完整的程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
List<List<Integer>> result=new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list=new ArrayList<Integer>();
backtracking(n,k,1,list);
return result;
}
public void backtracking(int n,int k,int start,List<Integer>list){
if(k<0) return ;
else if(k==0){
result.add(new ArrayList(list));
}else{
for(int i=start;i<=n;i++){
list.add(i);
backtracking(n,k-1,i+1,list);
list.remove(list.size()-1);
}
}
}
}

是不是有点想法了?那么我们操刀一下。

1
2
3
4
5
6
7
8
9
10
11
12
Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example,given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

(容我啰嗦地白话下,给你一个正数数组candidate[],一个目标值target,寻找里面所有的不重复组合,让其和等于target,给你[2,3,6,7] 2+2+3=7 ,7=7,所以可能组合为[2,2,3],[7])

按照前述的套路走一遍:

1
2
3
4
5
6
7
8
9
10
public class Solution {
List<List<Integer>> result=new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum(int[] candidates,int target) {
Arrays.sort(candidates);
List<Integer> list=new ArrayList<Integer>();
return result;
}
public void backtracking(int[] candidates,int target,int start, List<Integer> list){
}
}
  1. 全局List<List<Integer>> result先定义

  2. 回溯backtracking()要定义,数组candidates 目标target 开头start 辅助链表List list都加上。

  3. 分析算法:以[2,3,6,7] 每次尝试加入数组任何一个值,用循环来描述,表示依次选定一个值

  4. 1
    2
    3
    for (int i = start; i < candidates.length; i++){
    list.add(candidates[i]);
    }

接下来回溯方法再调用。比如第一次选了2,下次还能再选2是吧,所以每次start都可以从当前i开始(ps:如果不允许重复,从i+1开始)。第一次选择2,下一次要凑的数就不是7了,而是7-2,也就是5,一般化就是remain=target-candidates[i]所以回溯方法为:

backtracking(candidates,target-candidates[i],i,list);

然后加上退回语句:list.remove(list.size()-1);

那么什么时候找到的解符合要求呢?自然是remain(注意区分初始的target)=0了,表示之前的组合恰好能凑出target。如果remain<0 表示凑的数太大了,组合不可行,要回退。当remain="">0 说明凑的还不够,继续凑。

所以完整方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
List<List<Integer>> result=newArrayList<List<Integer>>();
public List<List<Integer>>combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);//所给数组可能无序,排序保证解按照非递减组合
List<Integer> list=newArrayList<Integer>();
backtracking(candidates,target,0,list);//给定target,start=0表示从数组第一个开始
return result;//返回解的组合链表
}
public void backtracking(int[]candidates,int target,int start,List<Integer> list){
if(target<0) return;//凑过头了
else if(target==0){
result.add(newArrayList<>(list));//正好凑出答案,开心地加入解的链表
}else{
for(inti=start;i<candidates.length;i++){//循环试探每个数
list.add(candidates[i]);//尝试加入
//下一次凑target-candidates[i],允许重复,还是从i开始
backtracking(candidates,target-candidates[i],i,list);
list.remove(list.size()-1);//回退
}
}
}
}

是不是觉得还是有迹可循的?下一篇博客将部分回溯算法拿出来,供大家更好地发现其中的套路。

链接如下:

回溯法欣赏


八皇后问题也是一个回溯法典型应用的场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class P5 {
static ArrayList<String[]> res;
public ArrayList<String[]> solveNQueens(int n) {
res = new ArrayList<String[]>();
if (n < 1) {
return res;
}
int[] cols = new int[n];
for (int i = 0; i < n; i++) {
cols[0] = i;
Strategy(cols, 1);
}
return res;
}
public void Strategy(int[] cols, int row) {
if (row == cols.length) {
String[] str = new String[cols.length];
for (int i = 0; i < cols.length; i++) {
str[i] = "";
for (int j = 0; j < str.length; j++) {
if (j == cols[i]) {
str[i]+="Q";
} else {
str[i]+=".";
}
}
}
res.add(str);
return;
}
for (int i = 0; i < cols.length; i++) {
if (isValid(cols, row, i)) {
cols[row] = i;
Strategy(cols, row+1);
}
}
}
public boolean isValid(int[] cols, int row, int col) {
if (cols == null) {
return false;
}
for (int i = 0; i < row; i++) {
if (cols[i] == col || Math.abs(col-cols[i]) == Math.abs(row-i)) {
return false;
}
}
return true;
}
}

dzzxjl

Home Java Python Linux ML Thoughts BookCan Links About