代码随想录算法训练营第二十九天| 491.递增子序列，46.全排列，47.全排列 II

题目与题解

491.递增子序列

题目链接：491.递增子序列

代码随想录题解：491.递增子序列

视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

解题思路：

        仍旧是组合题的回溯思路，但是有两个限制条件：一个是求序列，意味着数组顺序不可更改；二是求非递减序列，则要求后一个数不比前一个数小。

        递归三部曲：

        参数为 - 结果序列HashSet 的result，因为这里是有顺序的，所以结果唯一，可以用set去重；用于记录当前序列的list，数组nums和startIndex

        终止条件是按照非递减序列至少有两个元素，只要list中含有不止一个元素，就可以将其加入result并返回

        单层遍历条件为，如果list不为空且当前元素nums[i]不比list最后一个元素小，将其加入list，并用回溯函数对i+1之后的元素求解，再弹出list最后一个元素即可。

    class Solution {
        HashSet<List<Integer>> result = new HashSet<>();
        LinkedList<Integer> list = new LinkedList<>();

        public List<List<Integer>> findSubsequences(int[] nums) {
            findSubsequences(nums, 0);
            return new ArrayList<>(result);
        }

        public void findSubsequences(int[] nums, int startIndex) {
            if (list.size() > 1) {
                result.add(new ArrayList<>(list));
            }
            for (int i = startIndex; i < nums.length; i++) {
                if (list.isEmpty() || nums[i] >= list.getLast()) {
                    list.add(nums[i]);
                    findSubsequences(nums, i + 1);
                    list.pollLast();
                }
            }
        }
    }

看完代码随想录之后的想法 

        一开始不知道怎么去重，发现结果要求的是序列，所以想到可以用set去重，但是效率比较低。

        随想录直接用unordered set来记录元素在当前层有没有被使用，非常方便，根据nums[i]的范围直接用数组代替hashset效率更高。

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    private void backtracking (int[] nums, int start) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }

        int[] used = new int[201];
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                    (used[nums[i] + 100] == 1)) continue;
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

遇到的困难

        一开始去重只想用简单粗暴的方法，判断前后元素是否一样决定是否跳过本次循环，后来发现不行，因为序列本身并没有被排列过，也不能被排列，可能会出现后面的元素比前面小，但是后面元素可以跟更前面的元素组成序列的情况。这里要去重的其实是当前层的相同元素，抓住这一点就比较好做了。需要注意的是，树层还是树枝要去重，used数组或set使用的地方不一样。

46.全排列

题目链接：46.全排列

代码随想录题解：46.全排列

视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

解题思路：

        仍旧是回溯那一套，不同的地方在于，全排列是要把所有可能的组合都输出，且不一定是按顺序输出，所以startIndex就不需要了。

        回溯三部曲：参数为result，list，nums，和用于记录当前树枝元素使用情况的数组used，由于nums[i]仅仅在-10到10之间，且nums[i]中的元素不会重复，所以used可以初始化为21个全0元素；终止条件为list的元素数量与nums.length相同，表示每一个元素都已经取到了，将list加入result；单层遍历逻辑为，对于nums中的所有元素，如果used[nums[i]+10]被用过，直接跳过当前循环，否则将其加入list，调用回溯函数继续遍历nums，出来后将list最后一个元素弹出即可。

class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> list = new LinkedList<>();
	boolean[] used = new boolean[21];
    public List<List<Integer>> permute(int[] nums) {
		backTrace(nums);
		return result;
    }

	public void backTrace(int[] nums) {
		if (list.size() == nums.length) {
			result.add(new ArrayList<>(list));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (used[nums[i]+10]) continue;
			list.add(nums[i]);
			used[nums[i]+10] = true;
			backTrace(nums);
			used[nums[i]+10] = false;
			list.pollLast();
		}
	}
}

看完代码随想录之后的想法 

        受前一题影响写复杂了，只要用used[i]记录当前位置的元素是否有使用即可。

        也可以利用java里面linkedlist的特性，直接判断list是否contain 元素nums[i]替代used。

class Solution {

    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

遇到的困难

        全排列和以往的组合问题不同，每次回溯时元素都是从头开始找，不需要startIndex，并且需要判断树枝上的元素是否使用过，保证每个list的元素不重复不遗漏，所以used数组非常好用。一开始写的时候没有想清楚就容易出错。

47.全排列 II

题目链接：​​​​​​​47.全排列 II

代码随想录题解：​​​​​​​47.全排列 II

视频讲解：​​​​​​​回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

解题思路：

        这一题在上一题的基础上，多了一个不可有重复排列数组的要求，所以在原先树枝去重的基础上，还要加上树层去重，需要两个used数组来处理。

回溯三部曲：

        参数为result，list，nums，和用于记录当前树枝元素使用情况的数组used；

        终止条件同样为list的元素数量与nums.length相同，表示每一个元素都已经取到了，将list加入result；

        单层遍历逻辑为，在遍历前初始化usedCurrentLevel数组，考虑到nums[i]的范围，将其初始化大小为21；对于nums中的所有元素，如果used[i]或usedCurrentLevel[i]被用过，直接跳过当前循环，否则将其加入list，调用回溯函数继续遍历nums，出来后将list最后一个元素弹出即可。

class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
		Arrays.sort(nums);
		boolean[] used = new boolean[nums.length];
		backTrace(nums, used);
		return result;
    }

	void backTrace(int[] nums, boolean[] used) {
		if (list.size() == nums.length) {
			result.add(new ArrayList<>(list));
			return;
		}
		boolean[] usedCurrentLevel = new boolean[21];
		for (int i = 0; i < nums.length; i++) {
			if (used[i] || usedCurrentLevel[nums[i]+10]) continue;
			usedCurrentLevel[nums[i]+10] = true;
			list.add(nums[i]);
			used[i] = true;
			backTrace(nums, used);
			used[i] = false;
			list.pollLast();
		}
	}
}

看完代码随想录之后的想法 

        一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

        从实现上来说，又想复杂了，usedCurrentLevel数组完全可以由nums[i]==nums[i-1]代替，因为全排列数组是可以先排序再计算的，不影响结果。

        不过对于used[i-1]的true和false问题，有点费解，二刷再说吧。

class Solution {
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }
}

遇到的困难

        这题难就难在双重去重，但是前面其实做过很多类似的题目，将它们组合一下就可以了。

今日收获

        从组合问题正式步入排列问题的求解，有点难，但是还是比较套路。