兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

6.2 全検索

再帰と計算結果をうまく組み合わる、この発想がなかなか出てきません。

#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 がマイナス値になったら打ち切る判定を一応入れてみました。