【c语言】整数拆分

// 原作者箱庭，请勿转载

#include <stdio.h>

int n;          // 待分解的数
int nums[100];  // 存储每个组成部分的数值
int size;       // 当前组成部分的数量
int cnt;        // 分解方案的数量

// 深度优先搜索函数，cur为当前需要分解的数，sum为已分解的数之和，last为上一个加数
void dfs(int cur, int sum, int last) {
    // 如果已经成功分解出所有数且总和为n，则找到了一个分解方案
    if (cur == 0 && sum == n) {
        cnt++;  // 记录分解方案的数量
        // 输出分解方案
        printf("%d=%d", n, nums[0]);
        for (int i = 1; i < size; i++) {
            printf("+%d", nums[i]);
        }
        printf("n");
    } else {
        // 枚举所有可能的加数
        for (int i = 1; i <= cur; i++) {
            // 确保加数不小于上一个加数，总和不超过n，并且不能仅剩一个数未加入
            if (i >= last && sum + i <= n && i<n ) {
                nums[size] = i;  // 将当前加数存入组成部分
                size++;          // 组成部分数量加1
                dfs(cur - i, sum + i, i);  // 继续分解剩余部分
                size--;          // 回溯，撤销当前加数的选择
            }
        }
    }
}

//原作者箱庭，请勿转载

int main() {
    scanf("%d", &n);    // 输入待分解的数
    nums[0] = 0;        // 初始化组成部分，第一个数为0
    size = 0;           // 初始化组成部分数量
    dfs(n , 0, 1);      // 开始分解
    printf("%d", cnt);  // 输出分解方案数量
    return 0;
}