LeetCode 78.子集 和 46.全排列

1、题目

78题和46题可以一起看，一起做对比。两道题目都是用回溯算法求。但是递归参数有点区别。
78题：

image.png

46题：

image.png

2、分析

用回溯算法。可以结合后面的代码来看图
78题：

image.png

46题：

image.png

3、代码

78题代码：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> tack = new LinkedList<>();
        backTack(nums, 0, tack);
        return res;
    }

    public void backTack(int[] nums, int start, LinkedList<Integer> tack){
        res.add(new LinkedList<>(tack));
        //从start开始循环
        for(int i = start; i < nums.length; i++){
            tack.add(nums[i]);
            backTack(nums, i + 1, tack);
            tack.removeLast();
        }
    }
}

46题代码：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> tack = new LinkedList<>();
        dfs(nums, tack);
        return res;
    }

    private void dfs(int[] nums, LinkedList<Integer> tack){
        if(tack.size() == nums.length){
            res.add(new LinkedList<Integer>(tack));
            return;
        }
        //每一次都从0开始循环
        for(int i = 0; i < nums.length; i++){
            if(tack.contains(nums[i])) continue;
            tack.add(nums[i]);
            dfs(nums, tack);
            tack.removeLast();
        }
    }
}