leetcode的回溯算法題目用這個(gè)模板解題，一網(wǎng)打盡，so easy?。?！

這一篇文章來講解一下如何做leetcode回溯算法題目，這一段時(shí)間我把leetcode上面的回溯算法的題目都刷了個(gè)遍，發(fā)現(xiàn)了其中一些規(guī)律，所以，就想寫一篇文章來總結(jié)一下，怕以后忘記。

刷完回溯算法的題目，我發(fā)現(xiàn)其實(shí)可以總結(jié)為三大類：子集問題、組合問題、排列問題，那這三大類都是什么意思呢，我分別舉一個(gè)例子來說明。

子集問題，比如說，數(shù)組[1,2,3]，那么對應(yīng)的子集問題就是，這個(gè)數(shù)組的子集有：[],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3]，這就是這個(gè)數(shù)組的子集，這一類問題在leetcode上面很多個(gè)，而且有些題目數(shù)組中的元素是可以重復(fù)的，然后來求子集問題。

組合問題，比如說，數(shù)組[1,2,3]，組合出target為3的可能的選擇，那么就有：[1,2],[3]，這就是leetcode中的組合問題。

排列問題，排列問題就比較簡單了，比如，我們常見的全排列問題，leetcode也有這一類問題。

這篇文章，我們就來講講，怎么用回溯的算法去解決這些問題。

1 一步一步講解回溯算法框架

最開始，我還是想通過一個(gè)簡單的例子，一步一步的帶大家看一下回溯算法的題目應(yīng)該是怎么一步一步解決的，最終，通過這個(gè)題目，我們就可以大致的整理出一個(gè)回溯算法的解題框架；先來看下面這個(gè)題目，是一個(gè)子集的題目，題目難度中等。

這個(gè)題目，題目給的框架是這樣的。

????public?List>?subsets(int[]?nums)?{
????????????
????}

所以，我們就知道，我們先構(gòu)建一個(gè)List>類型的返回值。

????List>?list?=?new?ArrayList<>();

接下來，我們就開始寫回溯方法。

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????for(int?j?=?0;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

最開始，可能寫成上面這個(gè)樣子，傳入數(shù)組nums，start和temp集合用于保存結(jié)果，然后，每次遍歷數(shù)組nums的時(shí)候，都加入當(dāng)前元素，在遞歸回來的時(shí)候再回溯，刪除剛剛加入的元素，這不就是回溯的思想嗎。

這樣把基本的框架寫完了，還有一個(gè)需要思考的問題就是base case，那么這個(gè)題目的base case是什么呢？其實(shí)，因?yàn)槭亲蛹?，每一步都是需要加入到結(jié)果集合temp的，所以就沒有什么限制條件了。

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????//每次都保存結(jié)果
????????list.add(new?ArrayList<>(temp));
????????for(int?j?=?0;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

最后，我們再補(bǔ)充完整一下，就完整的代碼出來了。

????List>?list?=?new?ArrayList<>();
????public?List>?subsets(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?null;
????????}
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,?nums,?temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????list.add(new?ArrayList<>(temp));
????????for(int?j?=?0;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

ok，我們?nèi)ミ\(yùn)行一下，看看如何。

他說我超出時(shí)間限制，說明算法是有問題的，我們再看一下上面我們寫的代碼，我們發(fā)現(xiàn)，其實(shí)我們每次遍歷數(shù)組的時(shí)候都是從0開始遍歷的，導(dǎo)致很多重復(fù)的元素遍歷了，也就是我們得start變量并沒有用到，最后，我們把遍歷的時(shí)候不每次從0開始，而是從當(dāng)前的start開始遍歷，選過的元素我們排除，看一下結(jié)果。

????List>?list?=?new?ArrayList<>();
????public?List>?subsets(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?null;
????????}
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,?nums,?temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????list.add(new?ArrayList<>(temp));
????????//從start開始遍歷，避免重復(fù)
????????for(int?j?=?start;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

發(fā)現(xiàn)完美通過，good job??！

另外，我們要注意一個(gè)點(diǎn)就是：list.add(new ArrayList<>(temp));不要寫成list.add(temp);，否則，輸出的結(jié)果就是空集，你思考一下應(yīng)該就知道為什么了。

通過，這個(gè)題目，其實(shí)，我們就把回溯算法的一個(gè)大致的框架可以整理出來了，以后做其他題目，照貓畫虎，一頓操作就可以了。

回到backTrace函數(shù)，其實(shí)就是一個(gè)選擇/撤銷選擇的過程，其中的for循環(huán)也是一個(gè)選擇的過程，還有一個(gè)點(diǎn)就是base case需要在這個(gè)函數(shù)來處理。那么，我們就可以把框架整理出來。

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????base?case處理
????????//選擇過程
????????for(循環(huán)選擇){
????????????選擇
????????????backTrace(遞歸);
????????????撤銷選擇
????????}
????}

ok，上面已經(jīng)講了一個(gè)子集的問題，接下來，再來一個(gè)更有點(diǎn)意思的子集的題目。

2 子集問題

用于引入回溯算法框架的那個(gè)題目其實(shí)比較簡單，但是，思想是不變的，這個(gè)框架很重要，其他的題目基本上都是在上面的框架上進(jìn)行修改的，比如，剪枝操作等。

90. 子集 II 中等難度

這個(gè)題目與前面的子集題目相比較，差別就在于補(bǔ)鞥呢包含重復(fù)的子集，也就是不能順序改變而已，元素一樣的子集出現(xiàn)。

這個(gè)題目框架還是不變的，但是，要做一下簡單的剪枝操作：怎么排除掉重復(fù)的子集。

這里有兩種方法可以解決這個(gè)問題，而且，后面其他的題目出現(xiàn)不能出現(xiàn)重復(fù)子集這樣的限制條件的時(shí)候，都是可以用這兩種方法進(jìn)行解決的。

• 方法一：利用Set去重特性解題

我們還是先把上面的框架搬下來，然后再進(jìn)行修改。

????List>?list?=?new?ArrayList<>();
????public?List>?subsets(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?null;
????????}
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,?nums,?temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????list.add(new?ArrayList<>(temp));
????????//從start開始遍歷，避免重復(fù)
????????for(int?j?=?start;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

因?yàn)槲覀円肧et的特性去重，所以需要加入這個(gè)變量Set> set = new HashSet<>();，另外，為了保證順序，我們再進(jìn)行排序Arrays.sort(nums)，這樣能避免元素一樣，但是順序不一樣的重復(fù)子集問題。

所以，結(jié)果就出來了。

????List>?list?=?new?ArrayList<>();
????Set>?set?=?new?HashSet<>();
????public?List>?subsetsWithDup(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?null;
????????}
????????//排序
????????Arrays.sort(nums);
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,?nums,?temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????//set去重操作
????????if(!set.contains(temp)){
????????????set.add(new?ArrayList<>(temp));
????????????list.add(new?ArrayList<>(temp));
????????}
????????
????????for(int?j?=?start;?j?????????????temp.add(nums[j]);
????????????backTrace(j+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

看一下結(jié)果發(fā)現(xiàn)效率不是很好。

那我們再來看一下另外一種剪枝的策略用來去重。

• 方法二：i > start && nums[i-1] == nums[i]

這種剪枝策略為什么是可以的呢，別急，我來畫張圖解釋一下。

所以，我們這種方法就可以做出來了。

????List>?list?=?new?ArrayList<>();
????public?List>?subsetsWithDup(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?null;
????????}
????????Arrays.sort(nums);
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,?nums,?temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?nums,?List?temp){
????????list.add(new?ArrayList<>(temp));
????????
????????for(int?i?=?start;?i?????????????//剪枝策略
????????????if(i?>?start?&&?nums[i]?==?nums[i-1]){
????????????????continue;
????????????}
????????????temp.add(nums[i]);
????????????backTrace(i+1,nums,temp);
????????????temp.remove(temp.size()-1);
????????}
????}

哎呦，好像還可以哦。

3 組合問題

把前面的子集問題搞定之后，你會發(fā)現(xiàn)，后面的組合問題，排列問題就都不是什么大問題了，基本上都是套路了。

39. 組合總和 難度中等

這個(gè)題目跟之前的沒有什么太大的區(qū)別，只是需要注意一個(gè)點(diǎn)：每個(gè)數(shù)字可以被無限制重復(fù)被選取，我們要做的就是在遞歸的時(shí)候，i的下標(biāo)不是從i+1開始，而是從i開始。

????backTrace(i,candidates,target-candidates[i],?temp);

我們看看完整代碼。

????List>?list?=?new?ArrayList<>();
????public?List>?combinationSum(int[]?candidates,?int?target)?{
????????if(candidates.length?==?0?||?target?0){
????????????return?list;
????????}
????????List?temp?=?new?ArrayList<>();
????????backTrace(0,candidates,target,temp);
????????return?list;
????}

????public?void?backTrace(int?start,?int[]?candidates,?int?target,?List?temp){
????????//遞歸的終止條件
????????if?(target?0)?{
????????????return;
????????}

????????if(target?==?0){
????????????list.add(new?ArrayList<>(temp));
????????}?

????????for(int?i?=?start;?i?????????????temp.add(candidates[i]);
????????????backTrace(i,candidates,target-candidates[i],?temp);
????????????temp.remove(temp.size()-1);
????????}
????}

就是這么簡單！??！

那么，再來一個(gè)組合問題。

40. 組合總和 II 難度中等

你一看題目是不是就發(fā)現(xiàn)，差不多啊，確實(shí)，這里只是每個(gè)數(shù)字只能用一次，同時(shí)也是不能包含重復(fù)的組合，所以，用上面的去重方法解決咯。話不多說，上代碼。

????List>?lists?=?new?LinkedList<>();
????public?List>?combinationSum2(int[]?candidates,?int?target)?{
????????if(candidates.length?==?0?||?target?0){
????????????return?lists;
????????}
????????Arrays.sort(candidates);
????????List?list?=?new?LinkedList<>();
????????backTrace(candidates,target,list,?0);

????????return?lists;
????}

????public?void?backTrace(int[]?candidates,?int?target,?List?list,?int?start){
????????if(target?==?0){
????????????lists.add(new?ArrayList(list));
????????}
????????
????????for(int?i?=?start;?i?????????????if(target?0){
????????????????break;
????????????}
????????????//剪枝：保證同一層中只有1個(gè)相同的元素，不同層可以有重復(fù)元素
????????????if(i?>?start?&&?candidates[i]?==?candidates[i-1]){
????????????????continue;
????????????}
????????????list.add(candidates[i]);
????????????backTrace(candidates,target-candidates[i],list,i+1);
????????????list.remove(list.size()-1);
????????}
????}

也是完美解決！！

4 全排列問題

先來一個(gè)最基本的全排列問題，快速解決。

46. 全排列 難度中等

這是全排列，只是元素的順序不一樣，所以，我們要做的剪枝就是：temp集合中有的就排除。

上代碼。

????List>?lists?=?new?ArrayList<>();
????public?List>?permute(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?lists;
????????}
????????List?list?=?new?ArrayList<>();

????????backTrace(nums,list,0);

????????return?lists;
????}

????public?void?backTrace(int[]?nums,?List?temp,?int?start){
????????if(temp.size()?==?nums.length){
????????????lists.add(new?ArrayList(temp));
????????????return;
????????}

????????for(int?i?=?0;?i?????????????//排除已有元素
????????????if(temp.contains(nums[i])){
????????????????continue;
????????????}
????????????temp.add(nums[i]);
????????????backTrace(nums,temp,i+1);
????????????temp.remove(temp.size()?-?1);
????????}
????}

是不是不帶勁，安排?。?/p>

47. 全排列 II 難度中等

這個(gè)題目雖然也是全排列，但是，就要比前面這個(gè)難一些了，有兩個(gè)限定條件：有重復(fù)元素，但是不能包含重復(fù)排列。

不重復(fù)的全排列這個(gè)我們知道怎么解決，用前面的去重方法即可，但是，怎么保證有相同元素的集合不出現(xiàn)重復(fù)的排列呢？

這里我們需要加一個(gè)visited數(shù)組，來記錄一下當(dāng)前元素有沒有被訪問過，這樣就可以解題了。

??public?List>?result?=?new?ArrayList<>();
????public?List>?permuteUnique(int[]?nums)?{
????????if(nums.length?==?0){
????????????return?result;
????????}
????????Arrays.sort(nums);
????????findUnique(nums,new?boolean[nums.length],new?LinkedList());
????????return?result;
????}
????public?void?findUnique(int[]?nums,?boolean[]?visited,List?temp){
????????//結(jié)束條件
????????if(temp.size()?==?nums.length){
????????????result.add(new?ArrayList<>(temp));
????????????return?;
????????}
????????//選擇列表
????????for(int?i?=?0;?i????????????//已經(jīng)選擇過的不需要再放進(jìn)去了
????????????if(visited[i])?continue;
????????????//去重
????????????if(i>0?&&?nums[i]?==?nums[i-1]?&&?visited[i-1])?break;
????????????
????????????temp.add(nums[i]);
????????????visited[i]?=?true;

????????????findUnique(nums,visited,temp);

????????????temp.remove(temp.size()-1);
????????????visited[i]?=?false;
????????}
????}

這樣就搞定了這個(gè)題目。

5 不是總結(jié)

至此，就把子集、組合、全排列問題給解決了。從一步一步講解框架，到具體問題分析，面面俱到，哈哈，當(dāng)然，還有一些沒有考慮周到的地方，望大家指教。

這篇文章寫了兩天了，到這里差不多了，原創(chuàng)不易，點(diǎn)個(gè)贊吧！