整數拆分問題：遞歸與非遞歸實現輸出所有加法分解組合

整數拆分問題：遞歸與非遞歸實現輸出所有加法分解組合

給定正整數 n，輸出所有將 n 拆分為若干正整數之和的組合（順序不敏感，即 1+2 與 2+1 視為同一拆分）。例如 n=4 輸出：1+1+1+1、1+1+2、1+3、2+2、4。本文提供三種 C 語言實現：遞歸深度優先搜索、遞歸回溯優化、非遞歸迭代法。

方法一：遞歸 DFS（標準回溯）

void divide(int i, int n) {
    printf("%d", i);
    for (int j = 0; j < t; j++) printf("+%d", i);
    printf("+%d\n", n - i);
    if (n - i <= i) return;
    t++;
    divide(i, n - i);
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n/2; i++) { t = 0; divide(i, n); }
}

t 記錄當前加數 i 的重複次數，遞歸處理剩餘值 n-i，保證拆分序列非遞減，避免重複。

方法二：遞歸回溯（自底向上構建）

int num(int a, int i, int n) {
    if (a <= 0) return a;
    int k = num(a - i, i, n + i) + i;
    for (int j = i; j <= n; j += i) printf("%d+", i);
    printf("%d\n", k);
    return k;
}
int main() {
    int number; scanf("%d", &number);
    for (int n = 1; n <= number/2; n++) num(number - n, n, n);
}

通過遞歸返回值構建拆分項，參數 n 控制輸出格式，邏輯較晦澀但體現遞歸「分治」思想。

方法三：非遞歸迭代（數學規律直接構造）

void divide(int i, int num, int n) {
    int t, flag = 0;
    if (n % i) { t = n % i; flag = 1; } else t = i;
    while (t < n) {
        for (int k = 0; k < num - 1; k++) printf("%d+", i);
        if (flag) printf("%d+%d\n", i, t);
        else printf("%d\n", t);
        t += i; num--;
    }
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n/2; i++) divide(i, n/i, n);
}

利用除法與取模直接計算每組拆分的項數與尾項，無遞歸開銷，效率最高，邏輯清晰：對每個起始加數 i，計算能組成多少個 i 及剩餘尾數。

複雜度與選擇建議

• 時間複雜度均為 O(p(n))，p(n) 為分割數（指數級增長），輸出本身即為瓶頸。
• 空間：遞歸法 O(n) 棧深度，非遞歸法 O(1)。
• 工程推薦：非遞歸迭代法，無棧溢出風險，邏輯直觀，易於擴展（如統計拆分數、求最大乘積拆分等）。