heikki.salokanto
BAN USERThis seems to give the right answer, but the code isn't exactly very self-explanatory.
- heikki.salokanto August 11, 2015That works and it results in a relatively nice piece of code in Java 8 (and Guava).
public class Solver {
public static void main(String[] args) {
int input[] = {1, 3, 8};
int n = 70;
new Solver().solve(input, n);
}
private void solve(int[] input, int n) {
BitSet bitSet = new BitSet(n + 1);
Set<Integer> solution = IntStream.of(input).boxed()
.collect(Collectors.toSet());
for (int addedCount = 0; ; addedCount++) {
for (Set<Integer> combination : Sets.powerSet(solution)) {
int sum = combination.stream().mapToInt(i -> i).sum();
if (sum <= n) {
bitSet.set(sum);
}
}
if (bitSet.cardinality() > n) {
System.out.println("Added numbers: " + addedCount);
System.out.println("Final set: "
+ Ordering.natural().sortedCopy(solution));
return;
}
solution.add(bitSet.nextClearBit(1));
}
}
}
This doesn't work:
- heikki.salokanto August 18, 2015