90 Subsets II

https://leetcode.com/problems/subsets-ii/#/description

Given a collection of integers that might contain duplicates,nums, return all possible subsets.

Note:The solution set must not contain duplicate subsets.

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

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

分析及代码

排序+记录访问状况

public List<List<Integer>> subsetsWithDup(int[] nums) {
   List<List<Integer>> res = new ArrayList<>();
   int len = nums.length;
   Arrays.sort(nums);
   boolean[] used = new boolean[len];
   for(int i = 0; i <= len; i++) {
       generate(res, new ArrayList<>(), 0, i, nums, used);
   }
   return res;
}

private void generate(List<List<Integer>> res, List<Integer> cur, int index, int cnt, int[] nums, boolean[] used) {
    if(cur.size() == cnt) {
        res.add(new ArrayList<>(cur));
        return;
    }
    for(int i = index; i < nums.length; i++) {
        if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
            continue;
        }
        used[i] = true;
        cur.add(nums[i]);
        generate(res, cur, i + 1, cnt, nums, used);
        cur.remove(cur.size() - 1);
        used[i] = false;
    }
}