鉄則本 A18 - Subset Sum (3Q, ★3)

部分和問題。鉄則本の問題なので、コードのみ。

• 問題へのリンク

問題概要

個の整数 からいくつか選んで、総和を にすることが可能かどうかを判定せよ。

制約

• 
• 

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<vector<bool>> dp(N+1, vector<bool>(S+1, false));
    dp[0][0] = true;
    for (int i = 0; i < N; i++) {
        for (int s = 0; s <= S; s++) {
            if (!dp[i][s]) continue;
            dp[i+1][s] = true;
            if (s+A[i] <= S) dp[i+1][s+A[i]] = true;
        }
    }
    cout << (dp[N][S] ? "Yes" : "No") << endl;
}