【題解】ZeroJudge a522: 12455 – Bars

#include <iostream>
using namespace std;
int a[20];

int main() {
    int cases, target, sticks, num, tmp, i;
    bool flag;
    while (cin >> cases){
        while (cases--){
            cin >> target;
            cin >> sticks;
            for (int i = 0; i < sticks; i++){
                cin >> a[i];
            }
            num = 1;
            for (int i = 1; i < sticks; i++){
                num <<= 1;
                num++;
            }
            flag = false;
            for (int _i = 0; _i <= num; _i++){
                tmp = 0;
                i = _i;
                for (int j = 0; j < sticks; j++){
                    if (i & 1) tmp += a[j];
                    i >>= 1;
                }
                if (tmp == target){
                    flag = true;
                    break;
                }
            }
            if (flag) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

# 0 ≤ t ≤ 50，表示測資的筆數
t = int(input())
for iter1 in range(t):
    # 每筆測資三行，第一行有一個數字 n, 0 ≤ n ≤ 1000，表示我們所要的長度。
    n = int(input())
    # 第二行有一個數字 p, 1 ≤ p ≤ 20，表示我們所擁有的金屬棒的數量。
    p = int(input())
    # 第三行有 p 個數字，表示 p 根金屬棒的長度。
    P = list(map(int, input().split()))

    dp = [0 for i in range(n+1)]
    for i in P:
        for j in range(n, 0, -1):
            if (j >= i):
                dp[j] = max(dp[j], dp[j - i] + i)

    if (dp[n] == n):
        print("YES")
    else:
        print("NO")