代码随想录算法训练营Day22 | 491.非递减子序列、46.全排列、47.全排列||

LeetCode 491 非递减子序列

本题思路：什么情况下要搜集结果，可以写一个判断函数，当大小大于2的时候，并且，是非递减的，才能加入结果集中。需要注意的就是树层的一个去重操作。

class Solution {

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

    public void backtracking(int[] nums, int startIndex){
        if(isValid(path)){
            res.add(new ArrayList(path));
        }
        if(startIndex >= nums.length){
            return;
        }
        Set<Integer> set = new HashSet();
        for(int i = startIndex; i < nums.length; i++){
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }

    }

    public boolean isValid(List<Integer> path){
        if(path.size() < 2){
            return false;
        }
        for(int i = 1; i < path.size(); i++){
            if(path.get(i-1) > path.get(i)){
                return false;
            }
        }
        return true;
    }
}

LeetCode 46 全排列

本题思路: 全排列的话收集条件，就是 大小等于 nums.length的时候，需要注意的就是递归取元素的时候，不能取用过的元素。直接用一个全局的 set 集合，进行元素的去重。

class Solution {

    List<Integer> path = new ArrayList();
    List<List<Integer>> res = new ArrayList();
    Set<Integer> set = new HashSet();
    public List<List<Integer>> permute(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    public void backtracking(int[] nums, int index){
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = index; i < nums.length; i++){
            if(set.contains(nums[i])){
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums,0);
            path.remove(path.size() - 1);
            set.remove(nums[i]);
        }
    }
}

LeetCode 47 全排列||

本题思路：本题的数组元素有重复元素，所以要进行树层的一个去重操作。

class Solution {

    List<Integer> path = new ArrayList();
    List<List<Integer>> res = new ArrayList();

    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtracking(nums,0,used);
        return res;
    }

    public void backtracking(int[] nums,int index,int[] used){
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }      
        for(int i = index; i < nums.length; i++){
            // 树层去重
            if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0){
                continue;
            }
            // 树枝，去掉用过的元素
            if(used[i] == 1){
                continue;
            }
            path.add(nums[i]);
            used[i] = 1;
            backtracking(nums,0,used);
            path.remove(path.size() - 1);
            used[i] = 0;
        }
    }
}