江苏龙网

  1. 主页 > 生活百科 > >

回溯算法的题目，这样做，秒杀

回溯算法

【回溯算法的题目，这样做，秒杀】这一篇文章来讲解一下如何做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);        }    }


推荐阅读


上一篇：什么叫淘宝客pid 淘宝客pid在哪里

下一篇：淘宝老客户优惠券如何设置 淘宝怎么设置淘客优惠券