Day29题目

LeetCode491非递减子序列：

核心思想：也是回溯，但是不能使用排序去重，需要使用set。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        help(nums,0);
        return res;
    }
    public void help(int[] nums, int start){
        if(start > nums.length) return;
        if(path.size() > 1){
        	// 将所有子序列都加入
            res.add(new ArrayList<>(path));
        } 
        Set<Integer> set = new HashSet<>();
        for(int i = start; i < nums.length; i ++){
        	// 这里进行去重，当i大于start则是同一树层，如果set中存有这个数字则continue
            if(i>start && set.contains(nums[i])){
                continue;
            }
            if(path.isEmpty() || nums[i]>= path.getLast()){
                path.add(nums[i]);
                set.add(nums[i]);
                help(nums,i+1);
                // set不用回溯，因为每一树层在上面都自己创建了一个新的
                path.removeLast();
            }
        }
    }
}

LeetCode46全排列

核心思想：需要一个Boolean数组记录哪个使用过了，然后每次都从第一位开始遍历，这个没有去重，直接写回溯就ok

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[7];
    public List<List<Integer>> permute(int[] nums) {
        help(nums);
        return res;
    }
    public void help(int[] nums){
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0 ; i < nums.length;i++){
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            help(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

LeetCode47全排列Ⅱ：比上一题加上了去重

核心思想：还是使用了used数组，需要去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[9];
        Arrays.sort(nums);
        help(nums,used,0);
        return res;
    }
    public void help (int[] nums, boolean[] used, int count){
        if(count == nums.length) {
            res.add(new ArrayList<>(path));
        }
        for(int  i = 0; i < nums.length; i ++){
        	// 这里进行去重，在全排列中，只要是相同的元素，全排列结果就相同，因此只要有一个相同的元素就行了
        	// 我空想了一下，比如[1,1,1,2]的元素，最终加入结果集的1112是 nums[2] nums[1] nums[0] nums[3] 其他的被去重。 
            if( i > 0 && nums[i-1] == nums[i] && used[i-1] == true ){
                continue;
            }
            if(used[i] == false){
                path.add(nums[i]);
                used[i] = true;
                help(nums,used,count+1);
                used[i] = false;
                path.removeLast();
            }
        }
    }
}