經典算法題：部分和問題（DFS 遞歸解法）

經典算法題：部分和問題（DFS 遞歸解法）

問題描述：給定 n 個整數 a[0..n-1]，判斷能否從中選出若干數，使其和恰好等於 k。

解法分析

• 每個數只有兩種選擇：選 或 不選
• 共 2^n 種組合，適合深度優先搜索（DFS）暴力枚舉
• 時間複雜度 O(2^n)，適用於 n ≤ 20 的小規模數據
• 大規模數據需用動態規劃（DP）或會在中間相遇優化

遞歸 DFS 實現

#include <stdio.h>
#include <stdbool.h>

// 遞歸函數：考慮前 i 個數，當前和為 sum
bool dfs(int i, int sum, int *a, int n, int k) {
    if (i == n) return sum == k;           // 所有數考慮完，檢查是否達標
    if (dfs(i + 1, sum, a, n, k)) return true;      // 不選第 i 個
    if (dfs(i + 1, sum + a[i], a, n, k)) return true; // 選第 i 個
    return false;
}

void solve(int *a, int n, int k) {
    if (dfs(0, 0, a, n, k)) printf("Yes\n");
    else printf("No\n");
}

int main() {
    int a[] = {1, 2, 4, 7};
    int n = 4, k = 13;
    solve(a, n, k);  // 輸出 Yes (2+4+7=13)
    return 0;
}

執行流程圖解（以 a=[1,2,4,7], k=13 為例）

dfs(0,0)
├─ 不選1 → dfs(1,0)
│  ├─ 不選2 → dfs(2,0)
│  │  ├─ 不選4 → dfs(3,0)
│  │  │  ├─ 不選7 → dfs(4,0) → 0≠13 ✗
│  │  │  └─ 選7   → dfs(4,7) → 7≠13 ✗
│  │  └─ 選4   → dfs(3,4)
│  │     ├─ 不選7 → dfs(4,4) ✗
│  │     └─ 選7   → dfs(4,11) ✗
│  └─ 選2   → dfs(1,2)
│     ├─ 不選4 → dfs(2,2)
│     │  ├─ 不選7 → dfs(3,2) ✗
│     │  └─ 選7   → dfs(3,9) ✗
│     └─ 選4   → dfs(2,6)
│        ├─ 不選7 → dfs(3,6) ✗
│        └─ 選7   → dfs(3,13) → 13=13 ✓ 返回 true
└─ 選1 → ... (同理)

優化方向

1. 剪枝：若 sum > k 且全為正數，可直接返回 false
2. 記憶化搜索：用 memo[i][sum] 記錄狀態，避免重複計算
3. 動態規劃：dp[i][j] 表示前 i 個數能否湊出和 j，複雜度 O(n*k)
4. 會在中間：將數組分半，各枚舉所有子集和，雙指針查找，複雜度 O(2^(n/2))

DP 版本對比（適用於較大 k）

bool subset_sum_dp(int *a, int n, int k) {
    bool dp[k + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = k; j >= a[i]; j--) {
            if (dp[j - a[i]]) dp[j] = true;
        }
    }
    return dp[k];
}

總結

部分和問題是背包問題的特例，也是NP完全問題的經典代表。小數據用 DFS 暴力搜索代碼簡潔；大數據必須用 DP 或會在中間。面試中常考察：遞歸邏輯、剪枝優化、DP 轉換三個層次的理解。