ZOJ 1204 Additive Equations：DFS 枚舉所有加法等式

題目要求

給定 M (≤30) 個互不相同的正整數，找出所有形如 a1+a2+...+ak = b 的加法等式，其中左邊所有數及結果均屬於該集合。輸出按左邊項數升序，同項數按字典序排列；無解輸出 "Can't find any equations."。

深度優先搜尋策略

集合已排序。對每個可能的結果 a[i] (i≥2)，在前 i-1 個數中 DFS 選擇子集，若和等於 a[i] 則記錄方程。剪枝：當前和超過目標值即回溯。

去重與排序

DFS 保證左邊數字按升序選取，天然避免 1+2=3 與 2+1=3 重複。收集所有方程後，先按長度（項數+1），再按逐元素字典序排序。

核心代碼片段

void dfs(int idx, int len, int target) {
    if (idx == len) {
        if (cur_sum == target) {
            vector eq;
            for (int j = 0; j < len; ++j) if (chosen[j]) eq.push_back(chosen[j]);
            eq.push_back(target); // 最後一個元素存結果
            ans.push_back(eq);
            found = true;
        }
        return;
    }
    if (cur_sum + a[idx] <= target) {
        chosen[idx] = a[idx];
        cur_sum += a[idx];
        dfs(idx+1, len, target);
        cur_sum -= a[idx];
        chosen[idx] = 0;
    }
    dfs(idx+1, len, target);
}

主程序對每個測試案例清空狀態，排序輸入，枚舉目標值調用 DFS，最後按規則輸出。