当前位置: 代码迷 >> 综合 >> 部分和问题-dfs穷举
  详细解决方案

部分和问题-dfs穷举

热度:19   发布时间:2024-01-18 23:43:49.0

给定整数a1,a2,..am判断是否可以从中选出若干个数字,使得他们的和恰好为n

我们要判断每个数字选或者不选

#include <iostream>
using namespace std;
const int maxn=10005;
int a[maxn];
int n;
int sum;
bool dfs(int i,int cursum){if(i==n){return cursum==sum;}if(dfs(i+1,cursum+i)) return true;if(dfs(i+1,cursum)) return true;return false;
}
int main(int argc, char const *argv[])
{while(cin>>n){for(int i=1;i<=n;i++){cin>>a[i];}cin>>sum;dfs(0,0);}/* code */return 0;
}

给出一个数字n,写出1+..=n的所有加法形式


  相关解决方案