読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2717

algorithm algorithm-深さ優先探索 contest contest-codeIQ language language-c++

dfsで全探索する.

int n;
vector<int> a;

int dfs(int k, int sum)
{
  if(k==a.size()) return sum;
  int x = dfs(k+1,sum+a[k]);
  int y = dfs(k+1,sum);
  return abs(n-x)<abs(n-y)? x : y;
}

int main()
{
  int t; cin >> n;
  while(cin >> t) a.push_back(t);
  sort(a.begin(),a.end());
  cout << abs(n-dfs(0,0)) << endl;
  return 0;
}