使用回溯计算硬币数组的可能组合

Question

问题涉及以下内容。

对于给定的数组

int coins[2] = { 1, 2 };

它应该返回3。因为存在可能的组合。

1 + 1 + 1 + 1 = 4
1 + 1 + 2 = 4
2 + 2 = 4   

但是我的函数返回5，有什么想法吗？

int change(int coins[], int n, int sum, int index);

int main() { 
    int coins[2] = { 1, 2 };
    int c = change(coins, 2, 4, 0);
    printf("%d", c);
}

int change(int coins[], int n, int sum, int index) {
    if (sum == 0)
        return 1;
    if (sum < 0) {
        return -1;
    }

    for (int i = 0; i < n; i++) {
        if (coins[i] > sum)
            continue;
        int k = change(coins, n, sum - coins[i], index);
        if (k > -1)
            return k + 1;
    }
    return -1;
}

Answer 1

在调用您的函数的行代码中尝试此操作:

int c = change(coins,2,4,0) - 1;

并尝试不同的情况。