专栏名称: 吴师兄学算法

和程序员小吴一起从初学者的角度学习算法，以动画的形式呈现解题的思路。每周四篇原创文章，期待你的鉴赏！

LeetCode 的回溯算法题目用这个模板解题，一网打尽，so easy！！！

吴师兄学算法 · 公众号 · · 2020-11-17 10:00

正文

点击上方“ 五分钟学算法 ”，选择“星标”公众号

重磅干货，第一时间送达

这一篇文章来讲解一下如何做 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> subsets(int[] nums) {
            
    }

所以，我们就知道，我们先构建一个 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);
        }
    }

最开始，可能写成上面这个样子，传入数组 nums ， start 和 temp集合 用于保存结果，然后，每次遍历数组nums的时候，都加入当前元素，在递归回来的时候再回溯，删除刚刚加入的元素，这不就是回溯的思想吗。

这样把基本的框架写完了，还有一个需要思考的问题就是 base case ，那么这个题目的 base case 是什么呢？其实，因为是子集，每一步都是需要加入到结果集合 temp 的，所以就没有什么限制条件了。

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

最后，我们再补充完整一下，就完整的代码出来了。

    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，我们去运行一下，看看如何。

他说我超出时间限制，说明算法是有问题的，我们再看一下上面我们写的代码，我们发现，其实我们每次遍历数组的时候都是从0开始遍历的，导致很多重复的元素遍历了，也就是我们得 start 变量并没有用到，最后，我们把遍历的时候不每次从0开始，而是从当前的start开始遍历， 选过的元素我们排除 ，看一下结果。

    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开始遍历，避免重复
        for(int j = start; 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 temp){
        base case




    
处理
        //选择过程
        for(循环选择){
            选择
            backTrace(递归);
            撤销选择
        }
    }

ok，上面已经讲了一个子集的问题，接下来，再来一个更有点意思的子集的题目。

2 子集问题

用于引入回溯算法框架的那个题目其实比较简单，但是，思想是不变的，这个框架很重要，其他的题目基本上都是在上面的框架上进行修改的，比如，剪枝操作等。

90. 子集 II 中等难度

这个题目与前面的子集题目相比较，差别就在于补鞥呢包含重复的子集，也就是不能顺序改变而已，元素一样的子集出现。

这个题目框架还是不变的，但是，要做一下简单的剪枝操作： 怎么排除掉重复的子集 。

这里有两种方法可以解决这个问题，而且，后面其他的题目出现 不能出现重复子集 这样的限制条件的时候，都是可以用这两种方法进行解决的。

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

我们还是先把上面的框架搬下来，然后再进行修改。

    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开始遍历，避免重复
        for(int j = start; j             temp.add(nums[j]);
            backTrace(j+1,nums,temp);
            temp.remove(temp.size()-1);
        }
    }

因为我们要利用Set的特性去重，所以需要加入这个变量 Set > set = new HashSet<>(); ，另外，为了保证顺序，我们再进行排序 Arrays.sort(nums) ，这样能避免元素一样，但是顺序不一样的重复子集问题。

所以，结果就出来了。

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

看一下结果发现效率不是很好。

那我们再来看一下另外一种剪枝的策略用来去重。

方法二： 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 组合问题

把前面的子集问题搞定之后，你会发现，后面的组合问题，排列问题就都不是什么大问题了，基本上都是套路了。

39. 组合总和难度中等

这个题目跟之前的没有什么太大的区别，只是需要注意一个点： 每个数字可以被无限制重复被选取 ，我们要做的就是在递归的时候， i 的下标不是从 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);
        }
    }

就是这么简单！！！

那么，再来一个组合问题。

40. 组合总和 II 难度中等

你一看题目是不是就发现，差不多啊，确实，这里只是每个数字只能用一次，同时也是不能包含重复的组合，所以，用上面的去重方法解决咯。话不多说，上代码。

    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个相同的元素，不同层可以有重复元素
            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集合中有的就排除。