回溯算法：非递减子序列子集，这题的去重并不是通解！！！！

一、题目

二、分析

这道题是有重复元素的，我们需要做到单层去重。可以参考以下链接

回溯算法：子集2-CSDN博客但是，以往的去重我们都是利用used数组和对输入的数组进行排序才做到的，这道题要求我们求子序列，我们是无法先把输入数组排序的，那该如何做呢？

这题可以对每一层的元素都建立一个set集合，如果访问过的元素，就把他放入set。

三、代码

public class DiZengZiXuLie {
    @Test
    public void test(){
        int[] test={4,6,7,7,5,7};
        findSubsequences(test);
        System.out.println(res);
    }

    List<List<Integer>> res=new ArrayList<>();//定义结果集
    List<Integer> path=new ArrayList<>();//定义单个结果

    
    public List<List<Integer>> findSubsequences(int[] nums) {
       backtracking(nums,0);
       return res;
        
    }
    public void backtracking(int[] nums,int begin){
      if(path.size()>=2){
      res.add(new ArrayList<>(path));}
        if(begin==nums.length){
            return;
        }
        Set<Integer> set=new HashSet<>(nums.length);
        for (int i = begin; i < nums.length; i++) {
            if(i>0&&set.contains(nums[i])){//同层必须去重
                continue;
            }
            if(path.size()>0&&nums[i]<path.get(path.size()-1)){//不满足递增，跳过
                continue;
            }
            path.add(nums[i]);
            set.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}