如何使用回溯法求解最多N个奇数之和分解目标数的全部方式

问题核心约束 #

• 拆分对象：指定正整数
• 拆分项要求：所有项均为正奇数
• 项数限制：拆分使用的总项数≤N
• 默认约定：拆分不考虑顺序，如1+1+5和1+5+1属于同一种拆分，避免重复输出

现有代码问题分析 #

你提交的代码存在几个核心逻辑缺陷：

1. 每次递归都重新初始化了存储拆分项的数组、求和变量、计数变量，上一层递归的状态完全没有保留，没有实现回溯的核心逻辑——状态保存与回退
2. 没有做非降序限制，会输出大量重复的拆分结果
3. 递归终止条件逻辑不完整，未覆盖所有剪枝场景，返回值也未定义
4. 变量遍历逻辑有误，无法覆盖所有合法奇数组合，比如示例中的1+3+3拆分就无法被遍历到

正确回溯实现思路 #

回溯函数需要传递4个核心状态：

• 当前剩余待拆分的数值left
• 下一个可选的最小奇数start（用来保证拆分项非降序，避免重复输出）
• 当前已经使用的项数cnt
• 存储当前拆分路径的数组path

回溯执行逻辑：

1. 终止条件1：如果left == 0，说明找到合法拆分，直接输出当前path的内容，结束当前分支
2. 终止条件2：如果cnt == N或者start > left，当前分支不可能产生合法结果，直接返回剪枝
3. 遍历逻辑：从start开始，步长为2（保证取奇数），遍历所有≤left的奇数：
   • 将当前奇数加入path
   • 递归进入下一层：剩余值变为left - 当前奇数，下一层的start保持为当前奇数（保证非降序），已用项数+1
   • 回溯：进入下一轮循环即可自动覆盖path对应位置的数值，完成状态回退

修正后参考代码 #

#include <stdio.h>
#define MAX_N 100 // 可按需调整最大项数上限

int g_max_cnt; // 存储全局最大项数限制，也可作为参数传递

void backtrack(int left, int start, int cur_cnt, int path[]) {
    // 找到合法拆分，输出结果
    if (left == 0) {
        for (int i = 0; i < cur_cnt; i++) {
            if (i > 0) printf("+");
            printf("%d", path[i]);
        }
        printf("\n");
        return;
    }
    // 超过项数限制或当前可选奇数大于剩余值，剪枝
    if (cur_cnt >= g_max_cnt || start > left) {
        return;
    }
    // 遍历所有合法奇数
    for (int i = start; i <= left; i += 2) {
        path[cur_cnt] = i;
        // 递归下一层，start保持i避免重复拆分
        backtrack(left - i, i, cur_cnt + 1, path);
    }
}

int main() {
    int target = 7;
    g_max_cnt = 3;
    int path[MAX_N] = {0};
    printf("目标数=%d，最大项数=%d的合法奇数拆分：\n", target, g_max_cnt);
    backtrack(target, 1, 0, path);
    return 0;
}

以上代码输入target=7、g_max_cnt=3时，输出结果为：

1+1+5
1+3+3
7

完全符合示例要求。

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