Skip to content

Instantly share code, notes, and snippets.

@anil477
Created January 29, 2022 12:28
Show Gist options
  • Save anil477/c652b442c11309932fa326ae04d65745 to your computer and use it in GitHub Desktop.
Save anil477/c652b442c11309932fa326ae04d65745 to your computer and use it in GitHub Desktop.
90. Subsets II
class Solution {
// https://leetcode.com/problems/subsets-ii/
// 90. Subsets II
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> output = new LinkedList();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
rec(nums, output, new ArrayList<>(), 0, used);
return output;
}
public void rec(int[] input, List<List<Integer>> output, List<Integer> temp, int index, boolean[] used) {
output.add(new ArrayList<>(temp));
for (int i = index; i < input.length; i++) {
if (used[i]) continue;
if (i>0 && input[i] == input[i-1] && !used[i-1]) continue;
used[i] = true;
temp.add(input[i]);
rec(input, output, temp, i+1, used);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment