如何用唯一整数划分(1<<N)-1？回溯算法问题排查

问题描述 #

给定整数N，需用回溯算法对(1<<N)-1进行无重复整数的划分。例如N=3时，目标值为7，合法划分包括1+2+4=7、2+5=7、6+1=7、4+3=7、7=7，含重复整数的划分（如2+2+2+1=7）不合法。

用户实现的代码存在两个核心问题：运行时会出现总和超过目标值的情况，且存在重复整数的划分。原代码如下：

void btrack(int k, int N, int sum, int used, int rep) {
    //if (k > (N + 1)) exit(-1);
    //printf("called with k = %d, N = %d, sum = %d, used = %d, rep = %d\n", k, N, sum, used, 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 = 1; i <= (1 << N) - 1; i++) {
        if (!(used & 1 << i))
            btrack(i, N, sum + i, used, rep * 10 + i);
    }
}

问题根源分析 #

• sum与used标记不匹配：原函数中，传入的k被标记为已使用（used |= (1<<k)），但k对应的数值从未被加到sum中，导致后续递归的sum计算缺失数据，同时错误占用了used位，引发重复标记或漏加数值的问题。
• 未提前校验sum+i的合法性：循环中直接将sum+i传入递归，未判断该值是否超过目标，导致大量无效递归，甚至出现sum超过目标值的情况。
• 递归参数设计冗余：k参数的存在导致逻辑混乱，初始调用时的k既未被计入sum，又被占用used位，完全是多余的设计。

修正后的代码 #

#include <stdio.h>

void btrack(int N, int sum, int used, int rep) {
    const int target = (1 << N) - 1;
    // 找到合法划分，输出结果
    if (sum == target) {
        printf("ended with %d\n", rep);
        return;
    }
    // 总和超过目标，直接终止
    if (sum > target) {
        return;
    }
    // 遍历所有可能的未使用整数
    for (int i = 1; i <= target; i++) {
        // 跳过已使用的数
        if (used & (1 << i)) {
            continue;
        }
        // 提前判断加入当前数后是否超目标，避免无效递归
        if (sum + i > target) {
            continue;
        }
        // 递归：更新sum、used、rep
        btrack(N, sum + i, used | (1 << i), rep * 10 + i);
    }
}

// 测试调用示例
int main() {
    int N = 3;
    // 初始状态：总和0、无数字使用、记录为空
    btrack(N, 0, 0, 0);
    return 0;
}

修正说明 #

1. 移除冗余的k参数，改为在循环中直接遍历所有未使用的整数，确保每一个被选中的数都会被加到sum中，同时标记到used里，逻辑完全匹配。
2. 提前判断sum+i是否超过目标值，直接跳过无效的递归分支，提升效率并避免sum超标的情况。
3. 调整终止条件顺序，先判断是否找到合法划分，再判断是否超目标，逻辑更清晰。

测试N=3时，输出结果为：

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

对应合法划分7、1+6、2+5、3+4、1+2+4。若需要去掉1+6和6+1这类排列重复的结果，可以在函数中增加一个last参数，让循环从last+1开始遍历，避免重复组合。

内容的提问来源于stack exchange，提问作者dMight