部分和(简单dfs)

问题描述:

a1,a2,a3…an;

求是否存在一部分使得其和为k;

分析:

加和不加。dfs下潜即可。

题解:

#include <iostream>
#include <vector>
using namespace std;
int k,ans;
vector<int>vec;
//dfs
bool dfs(int n,int sum){
  if(sum>k) return false;
  if(n==k) {
    if(sum==k){
      return true;
    }
    else{
      return false;
    }
  }
  if(dfs(n+1,sum+vec[n])) return true;
  if(dfs(n+1,sum)) return true;
}
void solve(){
  if(dfs(0,0))
     cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
}
int main(int argc, char *argv[]) {
  
  cin>>k>>ans;
  int temp;
  
  //INPUT
  for(int i=0;i<k;i++){
    cin>>temp;
    vec.push_back(temp);
  }
  solve();
}