遞歸解決子集和問題：正確與錯誤代碼深度解析

問題背景

給定一個長度為 N 的數組和目標值 M，判斷是否存在若干元素之和等於 M。要求使用遞歸函數實現。

輸入輸出樣例

輸入：
5
1 2 3 4 5
12
輸出：
YES

兩種遞歸寫法對比

✅ 正確版本（減法思路）

void pd(int in[], int n, int k) {
    if (in[n] == k) { flag = 1; return; }
    else if (n == 0) return;
    else {
        pd(in, n-1, k);           // 不選第 n 個
        pd(in, n-1, k - in[n]);   // 選第 n 個，目標值減去該元素
    }
}

❌ 錯誤版本（加法思路）

void pd(int in[], int n, int k, int sum) {
    if (sum == k) { flag = 1; return; }
    else if (n == 0) return;   // 錯誤：n==0 時尚未處理 in[0]
    else {
        pd(in, n-1, k, sum);
        pd(in, n-1, k, sum + in[n]);
    }
}

錯誤原因分析

加法版本在 n==0 時直接返回，導致 in[0] 永不參與 sum 累加。正確的終止條件應為 n == -1。此外，減法版本先判斷 in[n]==k，邏輯更緊湊，最壞情況時間複雜度為 O(2^n)，但常數因子略優。