C++ 如何使用唯一数字对整型进行分区

您错误地使用了变量k.它似乎保存了您try 测试的最后一个值.递归的本质是您试图将问题分解为较小的问题，因此如果您想避免重复，则永远不应该在递归调用中使用相同的值.

取而代之的是从k+1开始循环:

#include <stdio.h>

void btrack(int k, int N, int sum, int used, int rep) {
    if (sum == (1 << N) - 1) {
        printf("ended with %d \n", rep);
        return;
    }
    if ((sum > (1 << N) - 1) || (used & 1 << k))
        return;
    used |= (1 << k);

    for (int i = k+1; i <= (1 << N) - 1; i++) {
        btrack(i, N, sum + i, used, rep * 10 + i);
    }
}

int main() {
    btrack(0, 3, 0, 0, 0);
}

输出:

ended with 124 
ended with 16 
ended with 25 
ended with 34 
ended with 7 

现在，这一切工作，直到你需要分区非常大的值.你的基数为10的rep值几乎立即变得无用，而你的used值则用完了位.当你想真正得到一个结果时，你需要搜索一个主要由零组成的位array.

另一种解决方案是将路径存储在数组中.它可能看起来像这样(半健壮但有点天真):

int run_foo(int value, int sum_parts[], int max_count, int count)
{
    if (count + 1 >= max_count)
        return 0;

    // Loop over all potential next values
    for (int next = sum_parts[count] + 1; next <= value / 2; next++) {
        sum_parts[count + 1] = next;
        if (!run_foo(value - next, sum_parts, max_count, count + 1))
            return 0;
    }

    // Print result
    if (sum_parts[count] < value) {
        for (int i = 1; i <= count; i++) {
            printf("%d + ", sum_parts[i]);
        }
        printf("%d\n", value);
    }
    return 1;
}

int foo(int value, int sum_parts[], int max_count)
{
    if (max_count < 1)
        return 0;
    sum_parts[0] = 0;
    return run_foo(value, sum_parts, max_count, 0);
}

int main()
{
    const int max_count = 10;
    int sum_parts[max_count];
    foo(15, sum_parts, max_count);
}

输出:

1 + 2 + 3 + 4 + 5
1 + 2 + 3 + 9
1 + 2 + 4 + 8
1 + 2 + 5 + 7
1 + 2 + 12
1 + 3 + 4 + 7
1 + 3 + 5 + 6
1 + 3 + 11
1 + 4 + 10
1 + 5 + 9
1 + 6 + 8
1 + 14
2 + 3 + 4 + 6
2 + 3 + 10
2 + 4 + 9
2 + 5 + 8
2 + 6 + 7
2 + 13
3 + 4 + 8
3 + 5 + 7
3 + 12
4 + 5 + 6
4 + 11
5 + 10
6 + 9
7 + 8
15

在这里，使用一个数组来存储当前值的路径，递归调用试图通过只使用大于上次使用的值的值来从剩余的值中构建一个值.这会使用更多的内存，但性能的伸缩性应该会更好.

请注意，由于数组本质上是一个堆栈，因此您可能根本不需要递归就可以实现此解决方案，只需额外小心一点.这是满分"Exercise for the Reader"分.