回溯---含有相同元素求子集

悠悠 2021-11-29 07:58 166阅读 0赞

### 含有相同元素求子集 ###

[90. Subsets II (Medium)][90. Subsets II _Medium]

For example,
    If nums = [1,2,2], a solution is:
    
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

#### 题目描述： ####

给定一个集合，集合中有重复元素，返回其所有的不重复子集。

#### 思路分析： ####

求集合的子集，用回溯法进行解决。由于有重复元素，那么我们先对集合进行排序，然后添加元素的时候，查看是否和前一个元素相同，如果相同并且前一个元素还没有被访问，那么就跳过。

#### 代码： ####

class Solution {
        public List<List<Integer>>subsetsWithDup(int []nums){
        List<List<Integer>>res=new ArrayList<>();
        List<Integer>list=new ArrayList<>();
        if(nums==null||nums.length==0)
            return res;
        Arrays.sort(nums); //排序
        boolean []visited=new boolean[nums.length];
        for(int size=0;size<=nums.length;size++){
            backtracking(0,size,nums,visited,res,list);
        }
        return res;
    }
    public void backtracking(int start,int size,int[]nums,boolean[]visited,List<List<Integer>>res,List<Integer>list){
        if(list.size()==size){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=start;i<nums.length;i++){
            if(i!=0&&nums[i]==nums[i-1]&&!visited[i-1])
                continue;
            list.add(nums[i]);
            visited[i]=true; //标记已经访问过
            backtracking(i+1,size,nums,visited,res,list);
            list.remove(list.size()-1);
            visited[i]=false;
        }
    }
    }

转载于:https://www.cnblogs.com/yjxyy/p/11114235.html

[90. Subsets II _Medium]: https://leetcode.com/problems/subsets-ii/description/