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

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，因为从该算法的角度来看，其他一切都是不变的。
我们的目标是 select 来自 a 的单个元素，其总和等于 target。当我们遇到这种情况时，我们就完成了，我们唯一的工作就是 show 解决方案。
只有当我们当前的 sum 仍然低于 target，并且我们还没有到达 a 的终点时，算法才能继续。
总是有两种可能性：使用当前元素或跳过它。两者都是递归调查的。
程序必须在 binary 的适当位置留零，否则会在 backtracking 的各个级别提供误导性结果。出于这个原因，首先调查 use 分支。

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

Finding subset sum recursively producing incorrect output

c

algorithm

recursion

subset-sum