ZeroJudge 解題筆記：a981. 求和問題

作者：王一哲
日期：2025年7月18日


ZeroJudge 題目連結：a981. 求和問題

解題想法

這題要用遞迴窮舉所有的組合，輸出其中符合條件的組合，並且要適當地剪枝，節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼，最後一筆測資超時。

Python 程式碼

最後一筆測資超時。

def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n，要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程，輸入目前檢測的 nums 索引值，加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解，印出選擇的數字，結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值，結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴，索引值加 1，total 加上此項的值
            choice[curr] = False  # 回溯，不選此項
            backtrack(curr + 1, total)  # 遞迴，索引值加 1，total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解，印出 -1
        
if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 1.2 s，記憶體約為 252 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;  // 讀取數量 n，要找的加總 m
vector<int> nums (30);  // 候選的數值
vector<bool> choice (30);  // 是否選這個數字
bool have_ans;  // 是否有解

/* 主要的解題過程，輸入目前檢測的 nums 索引值，加總 */
void backtrack(int curr, int total) {
    if (total == m) {  // 有解，印出選擇的數字，結束遞迴
        have_ans = true;
        bool first = true;  // 是否為首項
        for(int i=0; i<n; i++) {  // 掃過 n 個數字
            if (choice[i]) {  // 如果有選此項
                if (!first) printf(" ");  // 不是首項，先印空格
                first = false;  // 只要 choice[i] 為 true，此項改成 false
                printf("%d", nums[i]);
            }
        }
        puts("");  // 換行
        return;
    }
    if (curr == n || total > m) return;  // 已出界或是目標為負值，結束遞迴
    choice[curr] = true;  // 選此項
    backtrack(curr + 1, total + nums[curr]);  // 遞迴，索引值加 1，total 加上此項的值
    choice[curr] = false;  // 回溯，不選此項
    backtrack(curr + 1, total);  // 遞迴，索引值加 1，total 不變
}

int main() {
    while(scanf("%d %d", &n, &m) != EOF) {
        nums.resize(n);  // 依照 n 改變長度
        choice.resize(n);
        for(int i=0; i<n; i++) {
            scanf("%d", &nums[i]);
            choice[i] = false;
        }
        sort(nums.begin(), nums.end());
        have_ans = false;  // 是否有解
        backtrack(0, 0);  // 從索引值 0、加總 0 開始
        if (!have_ans) puts("-1");  // 如果無解，印出 -1
    }
    return 0;
}