Skip to content

Instantly share code, notes, and snippets.

@b27lu
Created February 11, 2014 03:00
Show Gist options
  • Save b27lu/8928565 to your computer and use it in GitHub Desktop.
Save b27lu/8928565 to your computer and use it in GitHub Desktop.
Subsets @ LeetCode
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
if(S == null)
return null;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
//empty set is the subset of any set
result.add(new ArrayList<Integer>());
//sort array to statisfy the requirement of non-descending order
Arrays.sort(S);
dfsWorker(S, 0, result, new ArrayList<Integer>());
return result;
}
public void dfsWorker(int[] S, int position, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp){
for(int i = position;i<S.length;i++){
temp.add(S[i]);
//call dfsWorker() recursively
dfsWorker(S, i+1, result, temp);
result.add((ArrayList<Integer>) temp.clone());
//remove current element from temp before next interation
temp.remove(Integer.valueOf(S[i]));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment