【c語言】整數拆分

將一個正整數n拆分成若幹個正整數的和（至少兩個數,n<=100）。

輸入格式:

一個正整數n

輸出格式:

若幹行，每行一個等式（數與數之間要求非降序排列）。最後一行給出解的總個數

輸入樣例:

在這裡給出一組輸入。例如：

4

輸出樣例:

4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4

最後一行的4表示總共有4個解。

主要思路： 使用深度優先搜索演算法。從n開始，每次枚舉所有可能的加數，如果加數滿足要求，則將其加入到組成部分中，繼續遞歸處理剩餘部分，直到剩餘部分被成功分解或者不滿足要求，然後回溯，撤銷當前加數的選擇，嘗試下一個加數。這樣就能夠窮舉所有可能的分解方案。 使用遞歸函數dfs()實現深度優先搜索。dfs()函數有三個參數：cur表示當前需要分解的數，sum表示已經分解的數之和，last表示上一個加數。當cur為0且sum為n時，找到了一個分解方案，將其輸出；否則，枚舉所有可能的加數，並對剩餘部分進行遞歸處理。 在dfs()函數中使用數組nums[]存儲每個組成部分的數值，使用變數size記錄當前組成部分的數量。在遞歸處理剩餘部分時，需要將當前加數加入組成部分，並遞歸處理剩餘部分，成功分解後回溯，撤銷當前加數的選擇。這裡使用回溯法可以避免重覆計算。

// 原作者箱庭，請勿轉載

#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;
}