再帰と計算結果をうまく組み合わる、この発想がなかなか出てきません。
#include <iostream> #include <vector> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) { cin >> A[i]; } } static inline bool solve(int A[], int i, int n, int m) { if (m == 0) { return true; } if (i < n && m > 0) { return solve(A, i + 1, n, m) || solve(A, i + 1, n, m - A[i]); } else { return false; } } int main() { int n; cin >> n; vector<int> A(n); inputArray(&A[0], n); int q; cin >> q; int m; bool ans; for (int i = 0; i < q; i++) { cin >> m; ans = solve(&A[0], 0, n, m); cout << (ans ? "yes" : "no") << endl; } return 0; }
solve の途中で m がマイナス値になったら打ち切る判定を一応入れてみました。