Skip to content

Instantly share code, notes, and snippets.

@mekilis
Last active March 21, 2020 17:52
Show Gist options
  • Save mekilis/9902826fe1fd254e2b44d8fb8453cf62 to your computer and use it in GitHub Desktop.
Save mekilis/9902826fe1fd254e2b44d8fb8453cf62 to your computer and use it in GitHub Desktop.
This function generates and returns all subsets of a list using iteration
private static List<List<Integer>> subsetIterative(List<Integer> elements) {
System.out.println("Subsets of " + elements);
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> subset;
String subsetBinary;
int numberOfElements = elements.size();
for (int i = 0; i < (1 << numberOfElements); i++) {
subsetBinary = convertToZeroPaddedBinaryString(i, numberOfElements);
subset = new ArrayList<>();
for (int j = 0; j < numberOfElements; j++) {
if (subsetBinary.charAt(j) == '1') {
subset.add(elements.get(j));
}
}
subsets.add(subset);
System.out.println(String.format("%s: %s", subsetBinary, subset));
}
return subsets;
}
private static String convertToZeroPaddedBinaryString(int number, int padWidth) {
return String.format("%" + padWidth + "s", Integer.toBinaryString(number)).replaceAll(" ", "0");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment