手把手教你<leetcode>中的回溯算法——多一点套路

你的名字 2022-06-15 04:56 126阅读 0赞

<leetcode>是一个很强大的OJ(OnlineJudge)[算法][Link 1]平台,其中不少题目都很经典。其中有一个系列的考察回溯算法，例如[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>>，因此

(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<Integer> list)\{\}中的内容。

**\[java\]** [view plain][] [copy][view plain]

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

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

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

![Center][]

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

所以完整的程序如下：

**\[java\]** [view plain][] [copy][view plain]

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

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

Combination Sum

Given a set ofcandidate numbers (***C***) and a target number (***T***), findall unique combinations in ***C*** where thecandidate numbers sums to***T***.

The **same** repeated numbermay be chosen from ***C*** unlimited numberof 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,)\{

（1）      全局List<List<Integer>> result先定义

（2）      回溯backtracking方法要定义，数组candidates 目标target 开头start 辅助链表List<Integer> list都加上。

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

for(inti=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 说明凑的还不够，继续凑。

所以完整方法如下：

**\[java\]** [view plain][] [copy][view plain]

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

[Link 1]: http://lib.csdn.net/base/datastructure
[Combination Sum]: https://leetcode.com/problems/combination-sum/
[Subsets]: https://leetcode.com/problems/subsets/
[view plain]: http://blog.csdn.net/versencoder/article/details/52071930#
[Center]: /images/20220615/c3314c46aa4a495db83f87b597eec82f.png