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

• 标签: backtracking

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

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

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

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

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

首先我们来看一道题目：

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中选取两个数字的组合，包括图上所述的四种。）

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

public class Solution {
   public List<List<Integer>> combine(int n, int k) {

    }
}

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

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

定义一个全局的容器List<List<Integer>> result=new ArrayList<List<Integer>>();
定义一个辅助的方法（函数）public void backtracking(int n,int k, List<Integer>list){}n k 总是要有的吧，加上这两个参数，前面提到List<Integer> 是数字的组合，也是需要的吧，这三个是必须的，没问题吧。（可以尝试性地写参数，最后不需要的删除）
接着就是我们的重头戏了，如何实现这个算法？对于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){}中的内容。

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);调试后发现答案不对啊！为什么我的答案比他长那么多？

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

所以完整的程序如下：

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);  
            }  
       }  
    }  
}

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

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]）

按照前述的套路走一遍：

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){       
   }
}

全局List<List<Integer>> result先定义
回溯backtracking()要定义，数组candidates 目标target 开头start 辅助链表List list都加上。
分析算法：以[2,3,6,7] 每次尝试加入数组任何一个值，用循环来描述，表示依次选定一个值

for (int i = start; i < candidates.length; i++){
    list.add(candidates[i]);
}
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

接下来回溯方法再调用。比如第一次选了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 说明凑的还不够，继续凑。

所以完整方法如下：

```Java
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);//回退  
                }  
            }  
         
    }  
}

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

链接如下：

回溯法欣赏

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

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

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

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