Skip to content

Instantly share code, notes, and snippets.

@jingz8804
Last active August 29, 2015 13:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jingz8804/9486152 to your computer and use it in GitHub Desktop.
Save jingz8804/9486152 to your computer and use it in GitHub Desktop.
Subsets problem on LeetCode
import java.util.Arrays;
import java.util.ArrayList;
public class Subsets{
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
// sort the array first
Arrays.sort(S);
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> emptySet = new ArrayList<Integer>();
results.add(emptySet);
// get the real subsets
results = subsets(results, S, 0);
return results;
}
private ArrayList<ArrayList<Integer>> subsets(ArrayList<ArrayList<Integer>> results, int[] S, int currentInd){
if (S == null) return results;
if (S.length == 1 || currentInd == S.length - 1){
ArrayList<Integer> set = new ArrayList<Integer>();
set.add(S[currentInd]);
results.add(set);
return results;
}
int temp = S[currentInd];
results = subsets(results, S, currentInd + 1);
// use this constructor instead. Better not to create an empty ArrayList and copy each element's clone to it.
ArrayList<ArrayList<Integer>> newSets = new ArrayList<ArrayList<Integer>>(results);
for(ArrayList<Integer> former: results){
ArrayList<Integer> present = new ArrayList<Integer>(former);
present.add(0, temp);
newSets.add(present);
}
return newSets;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment