c - 递归地查找子集和，产生不正确的输出

Question

已关注 this method (pdf)实现递归解决方案，但我认为这是有问题的。我已经按照 pdf 文件中的描述完全实现了它。

下面的代码的输出是错误的。它显示了目标位置。目标数组包含应相加以获得总和的数字的位表示形式。

将 binary[i] = 1 放在 else if 条件中可以解决问题，但没有意义。

是否可以澄清什么是正确的解决方案？

#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];
void foo(int target, int i, int sum, int *a, int size) {
    binary[i] = 1;
    if (target == sum+a[i]) {
        int j;
        for (j=0;j<size;j++)
            printf("%d\n", binary[j]);
        return;
    } else if ((i+1 < size) && (sum + a[i] < target)) {
        foo(target, i+1, sum + a[i], a, size);
    }
    if ((i+1 < size) && (sum +a[i+1] <= target)) {
        binary[i] = 0;
        foo(target, i+1, sum, a, size);
    }
}

int main()
{
    int i, target =10,a[] = {1, 2, 3, 5, 100};
    foo(target, 0, 0, a, SIZE(a));
}

当前输出:0 1 1 1 1

预期输出:0 1 1 1 0

Answer 1

#include <stdio.h>

#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];

void show(int* p, int size) {
    int j;
    for (j = 0; j < size; j++)
        printf("%d\n", p[j]);
}

void foo(int target, int i, int sum, int *a, int size) {
    if (sum == target) {
        // solution found
        show(binary, size);
    } else if (sum < target && i < size) {
        // try both branches
        // 1. current value used
        binary[i] = 1;
        foo(target, i + 1, sum + a[i], a, size);
        // 2. current value skipped
        binary[i] = 0;
        foo(target, i + 1, sum, a, size);
    } else {
        // no solution on this path
    }
}

int main() {
    int target = 10;
    int a[] = {1, 2, 3, 5, 100};
    foo(target, 0, 0, a, SIZE(a));
}

说明:

• 我们只讨论 i、sum 和 binary，因为从该算法的角度来看，其他所有内容都是不变的。
• 我们的目标是从 a 中选择总和等于 target 的单个元素。当我们遇到这种情况时，我们就完成了，我们唯一的工作就是展示解决方案。
• 仅当当前总和仍低于目标且尚未到达a末尾时，算法才能继续进行.
• 总是有两种可能性:使用当前元素或跳过它。两者都被递归地研究。
• 该过程必须在二进制的适当位置保留零，否则会在 backtracking 的各个级别提供误导性结果。 。因此，首先会调查 use 分支。