A - Exhaustive Search

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_A (新しいタブで開く)

問題文

長さ $n$ の数列 $A$、整数 $m$。
$A$ の要素のいくつかの要素を足し合わせて $m$ が作れるか？
なお、各要素は 1 回だけ使える。

数列 $A$ が与えられたうえで、質問として $q$ 個の $m_i$ が与えられるので、 yes/no

制約

• $n \le 20$
• $q \le 200$
• $1 \le A_i \le 2,000$
• $1 \le m_i \le 2,000$

サンプル

I/O 1

5
1 5 7 10 21
4
2 4 17 8

no
no
yes
yes

考察

$n$ が小さめなので全探索。
使う / 使わないの bit 全探索。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_5_A/judge/6771394/C++17 (新しいタブで開く)

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  set<int> st;
  rep(bit, 1 << n) {
    int s = 0;
    rep(i, n) {
      if (bit & (1 << i)) s += a[i];
    }
    st.insert(s);
  }
  int q;
  cin >> q;
  while (q--) {
    int m;
    cin >> m;
    puts(st.count(m) ? "yes" : "no");
  }
  return 0;
}