アリ本 2-1 p34 部分和問題

ant-2-1-p34.cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 20;

int n, k;
int a[MAX_N];

bool dfs(int i, int sum)
{
  if (i == n)
    return sum == k;

  if (dfs(i + 1, sum))
    return true;

  if (dfs(i + 1, sum + a[i]))
    return true;

  return false;
}

void solve()
{
  if (dfs(0, 0))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

int main()
{
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }
  cin >> k;
  solve();
  return 0;
}