這一篇文章來講解一下如何做leetcode回溯算法題目，這一段時間我把leetcode上面的回溯算法的題目都刷了個遍，發現了其中一些規律，所以，就想寫一篇文章來總結一下，怕以后忘記。
刷完回溯算法的題目，我發現其實可以總結為三大類：子集問題、組合問題、排列問題，那這三大類都是什么意思呢，我分別舉一個例子來說明。
子集問題，比如說，數組[1,2,3]，那么對應的子集問題就是，這個數組的子集有：[],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3]，這就是這個數組的子集，這一類問題在leetcode上面很多個，而且有些題目數組中的元素是可以重復的，然后來求子集問題。
組合問題，比如說，數組[1,2,3]，組合出target為3的可能的選擇，那么就有：[1,2],[3]，這就是leetcode中的組合問題。
排列問題，排列問題就比較簡單了，比如，我們常見的全排列問題，leetcode也有這一類問題。
這篇文章，我們就來講講，怎么用回溯的算法去解決這些問題。
1 一步一步講解回溯算法框架
最開始，我還是想通過一個簡單的例子，一步一步的帶大家看一下回溯算法的題目應該是怎么一步一步解決的，最終，通過這個題目，我們就可以大致的整理出一個回溯算法的解題框架；先來看下面這個題目，是一個子集的題目，題目難度中等。
這個題目，題目給的框架是這樣的。
public List<List<Integer>> subsets(int[] nums) {
}
所以，我們就知道，我們先構建一個List<List<Integer>>類型的返回值。
List<List<Integer>> list = new ArrayList<>();
接下來，我們就開始寫回溯方法。
public void backTrace(int start, int[] nums, List<Integer> temp){
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
最開始，可能寫成上面這個樣子，傳入數組nums，start和temp集合用于保存結果，然后，每次遍歷數組nums的時候，都加入當前元素，在遞歸回來的時候再回溯，刪除剛剛加入的元素，這不就是回溯的思想嗎。
這樣把基本的框架寫完了，還有一個需要思考的問題就是base case，那么這個題目的base case是什么呢？其實，因為是子集，每一步都是需要加入到結果集合temp的，所以就沒有什么限制條件了。
public void backTrace(int start, int[] nums, List<Integer> temp){
//每次都保存結果
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
最后，我們再補充完整一下，就完整的代碼出來了。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
ok，我們去運行一下，看看如何。
他說我超出時間限制，說明算法是有問題的，我們再看一下上面我們寫的代碼，我們發現，其實我們每次遍歷數組的時候都是從0開始遍歷的，導致很多重復的元素遍歷了，也就是我們得start變量并沒有用到，最后，我們把遍歷的時候不每次從0開始，而是從當前的start開始遍歷，選過的元素我們排除，看一下結果。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//從start開始遍歷，避免重復
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
發現完美通過，good job！！
另外，我們要注意一個點就是：list.add(new ArrayList<>(temp));不要寫成list.add(temp);，否則，輸出的結果就是空集，你思考一下應該就知道為什么了。
通過，這個題目，其實，我們就把回溯算法的一個大致的框架可以整理出來了，以后做其他題目，照貓畫虎，一頓操作就可以了。
回到backTrace函數，其實就是一個選擇/撤銷選擇的過程，其中的for循環也是一個選擇的過程，還有一個點就是base case需要在這個函數來處理。那么，我們就可以把框架整理出來。
public void backTrace(int start, int[] nums, List<Integer> temp){
base case處理
//選擇過程
for(循環選擇){
選擇
backTrace(遞歸);
撤銷選擇
}
}
ok，上面已經講了一個子集的問題，接下來，再來一個更有點意思的子集的題目。
2 子集問題
用于引入回溯算法框架的那個題目其實比較簡單，但是，思想是不變的，這個框架很重要，其他的題目基本上都是在上面的框架上進行修改的，比如，剪枝操作等。
90. 子集 II 中等難度
這個題目與前面的子集題目相比較，差別就在于補鞥呢包含重復的子集，也就是不能順序改變而已，元素一樣的子集出現。
這個題目框架還是不變的，但是，要做一下簡單的剪枝操作：怎么排除掉重復的子集。
這里有兩種方法可以解決這個問題，而且，后面其他的題目出現不能出現重復子集這樣的限制條件的時候，都是可以用這兩種方法進行解決的。
- 方法一：利用Set去重特性解題
我們還是先把上面的框架搬下來，然后再進行修改。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//從start開始遍歷，避免重復
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
因為我們要利用Set的特性去重，所以需要加入這個變量Set<List<Integer>> set = new HashSet<>();，另外，為了保證順序，我們再進行排序Arrays.sort(nums)，這樣能避免元素一樣，但是順序不一樣的重復子集問題。
所以，結果就出來了。
List<List<Integer>> list = new ArrayList<>();
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
//排序
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
//set去重操作
if(!set.contains(temp)){
set.add(new ArrayList<>(temp));
list.add(new ArrayList<>(temp));
}
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
看一下結果發現效率不是很好。
那我們再來看一下另外一種剪枝的策略用來去重。
- 方法二：i > start && nums[i-1] == nums[i]
這種剪枝策略為什么是可以的呢，別急，我來畫張圖解釋一下。
所以，我們這種方法就可以做出來了。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int i = start; i < nums.length; 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 組合問題
把前面的子集問題搞定之后，你會發現，后面的組合問題，排列問題就都不是什么大問題了，基本上都是套路了。
39. 組合總和 難度中等
這個題目跟之前的沒有什么太大的區別，只是需要注意一個點：每個數字可以被無限制重復被選取，我們要做的就是在遞歸的時候，i的下標不是從i+1開始，而是從i開始。
backTrace(i,candidates,target-candidates[i], temp);
我們看看完整代碼。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return list;
}
List<Integer> temp = new ArrayList<>();
backTrace(0,candidates,target,temp);
return list;
}
public void backTrace(int start, int[] candidates, int target, List<Integer> temp){
//遞歸的終止條件
if (target < 0) {
return;
}
if(target == 0){
list.add(new ArrayList<>(temp));
}
for(int i = start; i < candidates.length; i++){
temp.add(candidates[i]);
backTrace(i,candidates,target-candidates[i], temp);
temp.remove(temp.size()-1);
}
}
就是這么簡單！！！
那么，再來一個組合問題。
40. 組合總和 II 難度中等
你一看題目是不是就發現，差不多啊，確實，這里只是每個數字只能用一次，同時也是不能包含重復的組合，所以，用上面的去重方法解決咯。話不多說，上代碼。
List<List<Integer>> lists = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return lists;
}
Arrays.sort(candidates);
List<Integer> list = new LinkedList<>();
backTrace(candidates,target,list, 0);
return lists;
}
public void backTrace(int[] candidates, int target, List<Integer> list, int start){
if(target == 0){
lists.add(new ArrayList(list));
}
for(int i = start; i < candidates.length; i++){
if(target < 0){
break;
}
//剪枝：保證同一層中只有1個相同的元素，不同層可以有重復元素
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 全排列問題
先來一個最基本的全排列問題，快速解決。
46. 全排列 難度中等
這是全排列，只是元素的順序不一樣，所以，我們要做的剪枝就是：temp集合中有的就排除。
上代碼。
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0){
return lists;
}
List<Integer> list = new ArrayList<>();
backTrace(nums,list,0);
return lists;
}
public void backTrace(int[] nums, List<Integer> temp, int start){
if(temp.size() == nums.length){
lists.add(new ArrayList(temp));
return;
}
for(int i = 0; i < nums.length; i++){
//排除已有元素
if(temp.contains(nums[i])){
continue;
}
temp.add(nums[i]);
backTrace(nums,temp,i+1);
temp.remove(temp.size() - 1);
}
}
是不是不帶勁，安排！！
47. 全排列 II 難度中等
這個題目雖然也是全排列，但是，就要比前面這個難一些了，有兩個限定條件：有重復元素，但是不能包含重復排列。
不重復的全排列這個我們知道怎么解決，用前面的去重方法即可，但是，怎么保證有相同元素的集合不出現重復的排列呢？
這里我們需要加一個visited數組，來記錄一下當前元素有沒有被訪問過，這樣就可以解題了。
public List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums.length == 0){
return result;
}
Arrays.sort(nums);
findUnique(nums,new boolean[nums.length],new LinkedList<Integer>());
return result;
}
public void findUnique(int[] nums, boolean[] visited,List<Integer> temp){
//結束條件
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return ;
}
//選擇列表
for(int i = 0; i<nums.length; i++){
//已經選擇過的不需要再放進去了
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;
}
}
這樣就搞定了這個題目。
5 不是總結
至此，就把子集、組合、全排列問題給解決了。從一步一步講解框架，到具體問題分析，面面俱到，哈哈，當然，還有一些沒有考慮周到的地方，望大家指教。
這篇文章寫了兩天了，到這里差不多了，原創不易，點個贊吧！
