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(); } } } }