共计 960 个字符，预计需要花费 3 分钟才能阅读完成。
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
难度：medium
题目：给定一可能含有重复元素的集合，返回所有可能的子集合。注意：答案不能含有重复子集。
思路：递归，排序去重
Runtime: 3 ms, faster than 45.31% of Java online submissions for Subsets II.Memory Usage: 35.7 MB, less than 0.97% of Java online submissions for Subsets II.
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
subsetsWithDup(nums, 0, i + 1, new Stack<Integer>(), result);
}
result.add(new ArrayList<>());
return result;
}
public void subsetsWithDup(int[] nums, int idx, int count, Stack<Integer> stack, List<List<Integer>> result) {
if (count <= 0) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = idx; i < nums.length – count + 1; i++) {
if (i == idx || nums[i – 1] != nums[i]) {
stack.push(nums[i]);
subsetsWithDup(nums, i + 1, count – 1, stack, result);
stack.pop();
}
}
}
}
