NYOJ 1058 部分和問題：DFS 深度優先搜尋解法詳解

題目描述

給定 n（1 ≤ n ≤ 20）個整數 a₁..aₙ 和目標和 K，判斷是否能從中選出若干數使其和恰好等於 K。若存在，按輸入順序輸出構成該和的數字（任意一組解即可），否則輸出 NO。

算法選擇：DFS 回溯

n ≤ 20，總子集數 2²⁰ ≈ 10⁶，適合用深度優先搜尋（DFS）枚舉所有子集。剪枝條件：當前累加和 sum > K 時直接返回。

狀態設計與遞歸邏輯

• pos：當前考慮的數組下標（避免重複組合）。
• sum：已選數字的和。
• vis[i]：標記第 i 個數字是否被選中。
• ok：全局標記是否已找到解（題目只需輸出一組）。

遞歸函數 DFS(pos)：
1. 若 sum ≥ K：sum == K 時輸出方案並設置 ok=1；返回。
2. 枚舉 i = pos .. n-1：選中 a[i]，更新 sum、vis，遞歸 DFS(i+1)，回溯恢復。

完整 C 代碼

#include <stdio.h>

int n, k, ok, arr[22], vis[22], sum;

void DFS(int pos) {
    if (sum >= k) {
        if (sum == k) {
            if (!ok) {
                ok = 1;
                printf("YES\n");
            }
            for (int i = 0; i < n; ++i)
                if (vis[i]) printf("%d ", arr[i]);
            printf("\n");
        }
        return;
    }
    for (int i = pos; i < n; ++i) {
        sum += arr[i];
        vis[i] = 1;
        DFS(i + 1);
        sum -= arr[i];
        vis[i] = 0;
    }
}

int main() {
    while (scanf("%d%d", &n, &k) == 2) {
        ok = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &arr[i]);
            vis[i] = 0;
        }
        sum = 0;
        DFS(0);
        if (!ok) printf("NO\n");
    }
    return 0;
}

樣例測試

輸入：
4 13
1 2 4 7

輸出：
YES
2 4 7

複雜度分析

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

常見坑點

• 輸出格式：YES 後換行，數字間有空格，末尾換行。
• 多組測試用例，直到 EOF。
• 若有多組解，題目接受任意一組；代碼中 ok 確保只輸出第一組。