和为定值的子集数
|递归|二叉树|
本题思维可以扩展到类似的题中，例如：子集和、子集积、排列组合类问题
其中：该题用到未知数组长度的读取，个人认为用stringstream会比之前的string然后一个一个读入方便很多
主要思想：对于子集类问题，无非就是对第i个元素进行决策，看其是否进入子集当中，因此本代码中的attemp(int i,int k)表示对第i个元素进行决策，并且当且决策的结果为k，决策成功的标志是k与目标结果相等：这就是为何要将目标定义为全局变量。其次，另一个if语句为剪枝内容。两个attempt个人认为可以理解为二叉树的两个分支，以此穷尽所有结果。
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream> //stringstream必要的头文件using namespace std;int m,a[10010],sum=0,n=0;
string s;void attempt(int i,int k){//目前处于第i个位置（未选）//目前和为kif(k==m){sum++;return;}if(k>m||i>=n){return;}//剪枝（将整个递归结构视为二叉树结构）attempt(i+1,k);//不将第i个数加入和中attempt(i+1,k+a[i]);//将第i个数加入和中return;
}int main(){getline(cin,s);stringstream ss(s);int num;while(ss>>num){a[n++] = num;}while(cin>>m){if(m==0){break;}sum = 0;attempt(0,0);cout<<sum<<endl;}return 0;
}