Skip to content

Instantly share code, notes, and snippets.

@whitipet
Created January 22, 2017 16:08
Show Gist options
  • Save whitipet/7c1daeaed1a4ae130f820c9392eea8ee to your computer and use it in GitHub Desktop.
Save whitipet/7c1daeaed1a4ae130f820c9392eea8ee to your computer and use it in GitHub Desktop.
Get all possible sums with indexes from array
import java.util.ArrayList;
import java.util.List;
public class PossibleSums {
public static List<Sum> getSumsList(final int[] numbersArray) {
final List<Sum> returnSumsList = new ArrayList<>();
final int numberOfSums = (int) Math.pow(2, numbersArray.length);
for (int i = 1; i < numberOfSums; i++) {
final Sum sum = new Sum();
final boolean[] mask = getMask(i);
for (int j = 0; j < mask.length; j++) {
if (mask[j]) {
sum.addToIndexes(j);
sum.addToSum(numbersArray[j]);
}
}
returnSumsList.add(sum);
}
return returnSumsList;
}
private static boolean[] getMask(final int digit) {
final String reversedBinaryString = new StringBuilder(Integer.toBinaryString(digit)).reverse().toString();
final boolean[] returnMask = new boolean[reversedBinaryString.length()];
for (int i = 0; i < reversedBinaryString.length(); i++)
returnMask[i] = reversedBinaryString.charAt(i) - '0' == 1;
return returnMask;
}
public static void printSumsList(final List<Sum> sums) {
System.out.println(new StringBuilder()
.append("Sums: ")
.append(sums.toString())
.append("\nItem count: ")
.append(sums.size())
);
}
public static class Sum implements Comparable<Sum> {
private final List<Integer> indexes = new ArrayList<>();
private int sum;
private Sum() {
}
private int getSum() {
return sum;
}
private void addToSum(final int value) {
sum += value;
}
private void addToIndexes(final int index) {
indexes.add(index);
}
@Override
public String toString() {
return String.valueOf(sum) + indexes;
}
@Override
public int compareTo(final Sum o) {
return this.sum - o.getSum();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment