ZeroJudge 解題筆記：c130. 00574 - Sum It Up

作者：王一哲
日期：2026年3月22日


ZeroJudge 題目連結：c130. 00574 - Sum It Up

解題想法

這題考自訂函式的遞迴與回溯，同時用 set 儲存已經測試的過組合。

Python 程式碼

使用時間約為 10 ms，記憶體約為 3.4 MB，通過測試。

import sys

def solve(line):  # 解題用的函式
    nums = list(map(int, line.split()))  # 讀取一行測資
    t, n = nums[0], nums[1]  # 前兩項是目標、可用數字數量
    nums = nums[2:]  # 後面是可用的數字
    tested = set()  # 已測試過的組合，要用 tuple
    result = [f"Sums of {t:d}:\n"]  # 答案開頭
    """ 回溯，代入已選數字、加總、起點索引值 """
    def backtrack(choice, total, start):
        if tuple(choice) in tested: return  # 已測試過，遞迴出口
        tested.add(tuple(choice))  # choice 轉成 tuple 加入 tested
        if total > t: return  # 加總大於目標，遞迴出口
        if total == t:  # 加總等於目標，新增一組解，遞迴出口
            result.append("+".join(map(str, choice)) + "\n")
            return
        for i in range(start, n):  # 依序測試 nums[start] ~ nums[n-1]
            backtrack(choice + [nums[i]], total + nums[i], i+1)  # 選擇 nums[i]
            backtrack(choice, total, i+1)  # 不選擇 nums[i]
    """ End of backtrack """
    backtrack([], 0, 0)  # 呼叫 backtrack，代入空串列、加總 0、起點 0
    if len(result) == 1: result.append("NONE\n")  # 如果 result 長度為 1，加入 NONE
    sys.stdout.write("".join(result))  # 輸出答案

if __name__ == "__main__":
    for line in sys.stdin:
        line = line.strip()
        if not line: continue
        if line == "0 0": break
        solve(line)

C++ 程式碼

使用時間約為 3 ms，記憶體約為 708 kB，通過測試。

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

int t, n;  // 目標、可用數字數量
vector<int> nums (20);  // 可用的數字
set<vector<int>> tested;  // 已測試過的組合
bool have_ans;  // 是否有解

/* 回溯，代入已選數字、加總、起點索引值 */
void backtrack(vector<int>& choice, int total, int start) {
    if (tested.count(choice) == 1) return;  // 已測試過，遞迴出口
    tested.insert(choice);  // choice 加入 tested
    if (total > t) return;  // 加總大於目標，遞迴出口
    if (total == t) {  // 加總等於目標，新增一組解，遞迴出口
        have_ans = true;
        int m = (int)choice.size();
        if (m == 1) {
            printf("%d\n", choice[0]);
        } else if (m == 2) {
            printf("%d+%d\n", choice[0], choice[1]);
        } else {
            for(int i=0; i<m-1; i++) printf("%d+", choice[i]);
            printf("%d\n", choice[m-1]);
        }
        return;
    }
    for(int i=start; i<n; i++) {  // 依序測試 nums[start] ~ nums[n-1]
        vector<int> tmp (choice.begin(), choice.end());
        tmp.push_back(nums[i]);
        backtrack(tmp, total + nums[i], i+1);  // 選擇 nums[i]
        vector<int> tmp2 (choice.begin(), choice.end());
        backtrack(tmp2, total, i+1);  // 不選擇 nums[i]
    }
}

int main() {
    while(scanf("%d %d", &t, &n) != EOF && (t != 0 || n != 0)) {
        nums.resize(n);
        for(int i=0; i<n; i++) scanf("%d", &nums[i]);
        tested.clear();
        printf("Sums of %d:\n", t);
        vector<int> choice;
        have_ans = false;
        backtrack(choice, 0, 0);  // 呼叫 backtrack，代入空串列、加總 0、起點 0
        if (!have_ans) puts("NONE");
    }
    return 0;
}