C语言无额外数据结构的回溯实现：正整数最大N项奇数拆分问题

实现思路 #

• 去重逻辑：限制每次选择的奇数≥上一次选中的奇数，保证拆分序列非降序，天然避免顺序不同的重复方案
• 回溯参数设计：无需引入复杂数据结构，仅用基础变量和固定大小数组即可实现：
  1. remain：当前剩余待拆分的整数值
  2. start：本次可选的最小奇数（保证非降序）
  3. cnt：当前已选中的奇数个数（用于校验不超过全局限制N）
  4. path[]：存储当前已选中的奇数序列，数组大小固定为全局常量N即可
• 剪枝规则：
  • 剩余值为0时直接输出有效方案
  • 剩余值<0 或 已选个数≥N时直接终止当前分支
  • 遍历可选奇数时仅遍历≤剩余值的奇数，避免无效递归

完整实现代码 #

#include <stdio.h>
// 全局常量N：限制拆分出的奇数最大个数，可按需修改
#define N 6
int g_target; // 存储原始输入的待拆分整数，用于格式化输出

void backtrack(int remain, int start, int cnt, int path[]) {
    // 找到有效拆分方案，格式化输出
    if (remain == 0) {
        printf("%d=%d", g_target, path[0]);
        for (int i = 1; i < cnt; i++) {
            printf("+%d", path[i]);
        }
        printf(", ");
        return;
    }
    // 剪枝：不符合条件直接返回
    if (remain < 0 || cnt >= N) {
        return;
    }
    // 遍历所有符合要求的奇数，保证≥start避免重复方案
    for (int i = start; i <= remain; i += 2) {
        path[cnt] = i;
        backtrack(remain - i, i, cnt + 1, path);
    }
}

void odd_split(int target) {
    if (target < 0) {
        printf("输入需为≥0的整数\n");
        return;
    }
    if (target == 0) {
        printf("0=\n");
        return;
    }
    g_target = target;
    int path[N] = {0};
    backtrack(target, 1, 0, path);
}

// 测试入口
int main() {
    int input;
    scanf("%d", &input);
    odd_split(input);
    return 0;
}

效果验证 #

当输入整数为7、全局常量N=6时，程序输出结果为：7=1+1+1+1+3, 7=1+1+5, 7=1+3+3, 7=7, ，与需求示例完全匹配，若需去除末尾多余逗号，可新增变量标记首个输出方案调整打印逻辑即可。

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