部分和问题

题目：给定整数a1,a2,..,an，判断是否可以从中选出若干数，使它们的和为k。n<=20

#include <iostream> using namespace std; int n,k,a[25]; bool dfs(int i,int sum); void solve(); int main() { while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; } cin>>k; solve(); } return 0; } void solve(){ if(dfs(0,0)) cout<<"yes\n"; else cout<<"no\n"; } bool dfs(int i,int sum){ if(i==n) return sum==k; if(dfs(i+1,sum)) return 1; if(dfs(i+1,sum+a[i])) return 1; return 0; }