Skip to content

Instantly share code, notes, and snippets.

@b27lu
Created February 11, 2014 03:50
Show Gist options
  • Save b27lu/8928977 to your computer and use it in GitHub Desktop.
Save b27lu/8928977 to your computer and use it in GitHub Desktop.
Subsets II @ LeetCode
public class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
if(num == null)
return null;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
result.add(temp);
//sort array to meet non-descending order requirement
Arrays.sort(num);
dfsWorker(num, 0, result, temp);
return result;
}
public void dfsWorker(int[] num, int position, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp){
for(int i = position;i<num.length;i++){
temp.add(num[i]);
//call dfsWorker() recursively
dfsWorker(num, i+1, result, temp);
result.add((ArrayList<Integer>) temp.clone());
//remove current elements before next iteration
temp.remove(Integer.valueOf(num[i]));
//skip duplicate elements to avoid duplicate subsets
while(i < num.length - 1 && num[i] == num[i+1])
i++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment