メモ

c = [list(input()) for _ in range(h)]

..#
.#.
↓
[['.', '.', '#'], ['.', '#', '.']]

def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m

for i in range(1, S // 3 + 1):
    result += mcomb(S - i * 3 + i - 1, i - 1)
    result %= m
print(result)

数列の長さが n の時に S - 3×n を n 個に分配する場合分けの数
n種類のものから重複を許してr個選ぶ場合の数はnHr=n+r−1Cr通り.

bit全検索

#入力を受け取る
N, W = map(int, input().split())
a = list(map(int, input().split()))

#bitが2^n通りの部分集合全体を動きます
exist = False
for bit in range(2**N):
    #部分集合に含まれる要素の和
    sum_val = 0
    for i in range(N):
        #i番目の要素a[i]が部分集合に含まれるかどうか
        if bit & (1 << i):
            sum_val += a[i]

    #sum_valがWに一致するかどうか
    if sum_val == W:
        exist = True

if exist:
    print("Yes")
else:
    pritn("No")

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n,w;
    cin >> n>>w;
    vector <int> a(n);
    for (int i=0;i<n;++i){
        cin >> a[i];
    }
    bool exist = false;
    for (int bit=0;bit<(1<<n);++bit){
        int sum = 0;
        for (int i=0;i<n;++i){
            if (bit & (1<<i)){
                sum += a[i];
            }
        }
        //cout << sum << endl;
        if (sum == w) exist=true;
    }
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}