3月20日：子集Ⅱ、非递减子序列

90.子集Ⅱ

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 

子集

（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

思路

题目与子集Ⅰ的不同之处是在保证解集中没有重复子集的同时数组中可能存在重复元素。首先应该对数组进行排序，然后在选择的时候，若没有选择上个元素而且上个元素和当前元素相同时，应当提前结束递归，因为集合里不会再出现这个元素，若选择了该重复元素则必定会出现重复子集。

    class Solution {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            dfs(false,0,nums);
            return res;
        }
        private void dfs(boolean choosePre,int cur,int[] nums){
            if(cur==nums.length){
                res.add(new ArrayList<>(path));
                return;
            }

            dfs(false,cur+1,nums);
            if(!choosePre&&cur>0&&nums[cur]==nums[cur-1]){
                return;
            }
            path.add(nums[cur]);
            dfs(true,cur+1,nums);
            path.remove(path.size()-1);

        }
    }

迭代写法：

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    ist<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        for(int mask=0;mask<(1<<n);mask++){
            path.clear();
            boolean flag=true;
            for(int i=0;i<n;i++){
                if((mask&(1<<i))!=0){
                    if(i>0&&(mask>>(i-1)&1)==0&&nums[i]==nums[i-1]){
                        flag=false;
                        break;
                    }
                    path.add(nums[i]);
                }
            }
            if (flag) {
                res.add(new ArrayList<>(path));
            }
        }
        return res;
    }
}

491.非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

思路

首先将每种可能的子集都列举出来，并且判断是否满足条件和是否重复，使序列合法的办法非常简单，就是给选择做一个限定条件，只有当前的元素大于等于上一个元素的时候才能选择当前元素。

那么如何保证没有重复呢？我们需要给不选择做一个限定条件，只有当前元素不等于上一个选择的元素时，才考虑不选择当前元素

因为如果有两个相同的元素，我们会考虑这样四种情况：

前者被选择，后者被选择
前者被选择，后者不被选择
前者不被选择，后者被选择
前者不被选择，后者不被选择
其中第二种情况和第三种情况其实是等价的，我们这样限制之后，舍弃了第二种，保留了第三种，于是达到了去重的目的。

class Solution {
            List<List<Integer>> res=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {
            dfs(Integer.MIN_VALUE,0,nums);
            return res;
        }
        private void dfs(int last,int cur,int[] nums){
            if(cur==nums.length){
                if(path.size()>=2){
                    res.add(new ArrayList<>(path));
                }
                return;
            }
            if(nums[cur]>=last){
                path.add(nums[cur]);
                dfs(nums[cur],cur+1,nums);
                path.remove(path.size()-1);
            }
            if(nums[cur]!=last){
                dfs(last,cur+1,nums);
            }
        }
}