私はこれを、別のサブセット和バリアントに与えた以前の回答から変更しました：https ://stackoverflow.com/a/10612601/120169
ここでは、上記の番号のK = 8のケースで実行しています。ここでは、2つの「カバレッジ」の1つに2つの異なる場所で1を再利用しています。それがあなたのためにどのように機能するか教えてください。
public class TurboAdder2 {
// Problem inputs
// The unique values
private static final int[] data = new int[] { 1, 2, 3, 4, 5 };
// counts[i] = the number of copies of i
private static final int[] counts = new int[] { 2, 1, 1, 1, 1 };
// The sum we want to achieve
private static int target = 8;
private static class Node {
public final int index;
public final int count;
public final Node prevInList;
public final int prevSum;
public Node(int index, int count, Node prevInList, int prevSum) {
this.index = index;
this.count = count;
this.prevInList = prevInList;
this.prevSum = prevSum;
}
}
private static Node sums[] = new Node[target+1];
// Only for use by printString and isSolvable.
private static int forbiddenValues[] = new int[data.length];
private static boolean isSolvable(Node n) {
if (n == null) {
return true;
} else {
while (n != null) {
int idx = n.index;
// We prevent recursion on a value already seen.
// Don't use any indexes smaller than lastIdx
if (forbiddenValues[idx] + n.count <= counts[idx]) {
// Verify that none of the bigger indexes are set
forbiddenValues[idx] += n.count;
boolean ret = isSolvable(sums[n.prevSum]);
forbiddenValues[idx] -= n.count;
if (ret) {
return true;
}
}
n = n.prevInList;
}
return false;
}
}
public static void printString(String prev, Node n, int firstIdx, int lastIdx) {
if (n == null) {
printString(prev +" |", sums[target], -1, firstIdx);
} else {
if (firstIdx == -1 && !isSolvable(sums[target])) {
int lidx = prev.lastIndexOf("|");
if (lidx != -1) {
System.out.println(prev.substring(0, lidx));
}
}
else {
while (n != null) {
int idx = n.index;
// We prevent recursion on a value already seen.
// Don't use any indexes larger than lastIdx
if (forbiddenValues[idx] + n.count <= counts[idx] && (lastIdx < 0 || idx < lastIdx)) {
// Verify that none of the bigger indexes are set
forbiddenValues[idx] += n.count;
printString((prev == null ? "" : (prev + (prev.charAt(prev.length()-1) == '|' ? " " : " + ")))+data[idx]+"*"+n.count, sums[n.prevSum], (firstIdx == -1 ? idx : firstIdx), idx);
forbiddenValues[idx] -= n.count;
}
n = n.prevInList;
}
}
}
}
public static void main(String[] args) {
for (int i = 0; i < data.length; i++) {
int value = data[i];
for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) {
for (int newsum = sum+1; newsum <= target; newsum++) {
if (sums[newsum - sum] != null) {
sums[newsum] = new Node(i, count, sums[newsum], newsum - sum);
}
}
}
for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) {
sums[sum] = new Node(i, count, sums[sum], 0);
}
}
printString(null, sums[target], -1, -1);
}
}