90. Subsets II
Last updated
Last updated
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
Arrays.sort(nums);
backtrack(subsets, new LinkedList<Integer>(), nums, 0);
return subsets;
}
private void backtrack(List<List<Integer>> subsets,
LinkedList<Integer> subset,
int[] nums,
int index) {
subsets.add(new ArrayList(subset));
for(int i = index; i < nums.length; i++) {
if (i > index && nums[i-1] == nums[i]) continue;
subset.add(nums[i]);
backtrack(subsets, subset, nums, i+1);
subset.removeLast();
}
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
subsets.add(new ArrayList());
Arrays.sort(nums);
for(int i = 0, start = 0, end = 0; i < nums.length; i++) {
start = 0;
if(i > 0 && nums[i-1] == nums[i]) {
start = end+1;
}
end = subsets.size()-1;
for(int j = start; j <= end; j++) {
List<Integer> subset = new ArrayList(subsets.get(j));
subset.add(nums[i]);
subsets.add(subset);
}
}
return subsets;
}
}