90. Subsets II (Medium)
https://leetcode.com/problems/subsets-ii/
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], [] ]
Solutions
class Solution {
Set<String> strSet = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
List<Integer> track = new ArrayList<>();
combine(0, nums, track, ans);
return ans;
}
private void combine(int depth, int[] nums, List<Integer> track, List<List<Integer>> ans) {
if (depth == nums.length) {
if (!strSet.add(track.toString())) {
return;
}
List<Integer> sol = new ArrayList<>(track);
ans.add(sol);
return;
}
track.add(nums[depth]);
combine(depth + 1, nums, track, ans);
track.remove(track.size()-1);
combine(depth + 1, nums, track, ans);
}
}