部分和問題：DFS 遞歸求解子集和等於 K

Challenge 2.1.4 部分和問題 - DFS 解法

問題：給定 n (≤20) 個整數，判斷是否存在子集和恰好等於 K。若存在輸出 "YES" 並按輸入順序輸出構成該和的數字，否則 "NO"。

DFS 遞歸思路

對每個數有「選」與「不選」兩種分支，遞歸枚舉所有子集（共 2ⁿ 種，n≤20 約 100 萬，可行）。

bool dfs(int i, int sum) {
    if (i == n) return sum == K;
    if (dfs(i+1, sum)) return true;           // 不選 a[i]
    if (dfs(i+1, sum + a[i])) return true;    // 選 a[i]
    return false;
}

輸出構成元素

需記錄選擇路徑。可用 path[] 數組標記是否選取，或在遞歸返回時構建輸出序列。

完整代碼（C++）

#include <iostream>
using namespace std;
#define MAX_N 30
int a[MAX_N], n, K, path[MAX_N];

bool dfs(int i, int sum) {
    if (i == n) return sum == K;
    if (dfs(i+1, sum)) return true;
    path[i] = 1;
    if (dfs(i+1, sum + a[i])) return true;
    path[i] = 0;
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> K;
    if (dfs(0, 0)) {
        cout << "YES\n";
        for (int i = 0; i < n; ++i)
            if (path[i]) cout << a[i] << ' ';
        cout << '\n';
    } else cout << "NO\n";
    return 0;
}

複雜度

時間 O(2ⁿ)，空間 O(n) 遞歸棧 + O(n) 路徑數組。n=20 時約 10⁶ 遞歸調用，極快。

優化提示

• 若數值非負，可加剪枝：sum > K 直接返回 false。
• 可用 meet-in-the-middle (n=40 時) 將複雜度降至 O(2^{n/2})。