问题:给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。解集不能包含重复的子集

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return res;
        }
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backtrack(nums, visited, 0, res, new ArrayList<Integer>());
        return res;
    }

    public void backtrack(int[] nums, boolean[] visited, int start, List<List<Integer>> res, List<Integer> tempList){
        res.add(new ArrayList<>(tempList));
        for(int i = start; i < nums.length; i++){
            //和上面引用的文章里分析的方法几乎一致,可见去重问题可以参考这个做法。
            if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
                continue;
            }
            if(!visited[i]){
                visited[i] = true;
                tempList.add(nums[i]);
                backtrack(nums, visited, i + 1, res, tempList);
                tempList.remove(tempList.size() - 1);
                visited[i] = false;
            }
        }
    }
}