程序的思想是:输入数据是,先使用快排对其从大到小进行排序,然后记录相同数据的个数,比如4 3 3 2 2 1 1,最后的数据变成4 3 2 1 ,并且同时数据的个数f[]变成1 2 2 2
然后就是遍历,相同的数据如果不能得到最后的结果,下一次就不会遍历。
//剪枝有这几个
首先:从大到小排序,剪枝1
再者:如果当前的sum比要遍历的数据小,则跳过这个数据
利用一个vector来记录结果
#include <iostream> //#include <fstream> #include <vector> #include <algorithm> using namespace std; /*0MS 344K*/ //function int cmp(const void *a,const void *b); void dfs(int index,int sum); //var int a[13]; //输入数据 int b[13]; //记录从大到小的数据,相同数据个数记录在f[]中 int l; //b[]数据的长度 int f[13]; //记录当前数据b[]的个数 vector<int> c; //结果 bool flag; //fstream fin; int main() { //fin.open("1258.txt",ios::in); int t,n; while(cin>>t>>n&&n!=0) { flag=false; for(int i=0;i<n;i++) { cin>>a[i]; } memset(f,0,sizeof(f)); qsort(a,n,sizeof(a[0]),cmp); //把相同的数据合并在一起 int cur=a[0]; //当前数据是多少 int j=0; b[j]=cur; for(int i=0;i<n;i++) { if(a[i]==cur) f[j]++; else { cur=a[i]; b[++j]=cur; i--; } } l=++j; cout<<"Sums of "<<t<<":"<<endl; dfs(0,t); if(!flag) cout<<"NONE"<<endl; } system("pause"); return 0; } void dfs(int index,int sum) { if(sum==0) { flag=true; int length=c.size(); for(int i=0;i<length-1;i++) cout<<c[i]<<"+"; cout<<c[length-1]<<endl; } else { for(int i=index;i<l;i++) { if(b[i]>sum) continue;//剪枝 else { c.push_back(b[i]); f[i]--; if(f[i]==0) dfs(i+1,sum-b[i]); else if(f[i]>0) dfs(i,sum-b[i]); f[i]++; c.pop_back(); } } } } int cmp(const void *a,const void *b) { return ((*(int *)b)-(*(int *)a)); }