用回溯法解决，需要找到一个限界条件来简化复杂度
此题限界条件为 (s+r-w[k])>=M && (s+w[k+1])<=M
子集和数
1 /*
2 子集和数问题
3 s代表目前选中的w[i]x[i]的结果，k代表选择的第几个数，r代表w[i]的和.
4 */
5 #include <iostream>
6 using namespace std;
7
8 int x[100];
9
10 void SumofSub(int s,int k,int r,int M,int *w)
11 {
12 x[k]=1;
13 if(s+w[k]==M) //如果等于M，那么输出结果
14 {
15 for(int i=0;i<=k;i++)
16 cout<<x[i]<<" ("<<w[i]<<")"<<endl;
17 cout<<endl;
18 }
19 else if(s+w[k]+w[k+1]<=M) //如果往后加两个元素，依然<=M，则将当前第k个元素加入s，k取下一个元素，继续递归
20 {
21 SumofSub(s+w[k],k+1,r-w[k],M,w);
22 }
23 if( (s+r-w[k])>=M && (s+w[k+1])<=M ) //如果不包括w[k]时，全体元素>=M,并且s加上下一个元素的和<=M，则舍弃当前第k个元素，选择下一个元素
24 {
25 x[k]=0;
26 SumofSub(s,k+1,r-w[k],M,w);
27 }
28 }
29
30 //快速排序/////////////////////////////////////////
31 void swap(int &a,int &b)
32 {
33 int temp = a;
34 a = b;
35 b = temp;
36 }
37
38 int partition(int *w,int p,int r)
39 {
40 int i=p-1;
41 int j=p;
42 for(j=p;j<r;j++)
43 {
44 if(w[j]<=w[r])
45 {
46 i++;
47 swap(w[i],w[j]);
48 }
49 }
50 swap(w[i+1],w[r]);
51 return i+1;
52 }
53
54 void QuickSort(int *w,int p,int r)
55 {
56 int q;
57 if(p<r)
58 {
59 q = partition(w,p,r);
60 QuickSort(w,p,q-1);
61 QuickSort(w,q+1,r);
62 }
63 }
64 //////////////////////////////////////////////////
65
66
67
68
69 int main()
70 {
71 int n,sum=0,M;
72 cout<<"输入数字个数:"<<endl;
73 cin>>n;
74 cout<<"请输入"<<n<<"个数字:"<<endl;
75 int *w = new int[n];
76 for(int i=0;i<n;i++)
77 {
78 cin>>w[i];
79 sum+=w[i];
80 }
81 cout<<"请输入要匹配的和的大小M:"<<endl;
82 cin>>M;
83 QuickSort(w,0,n-1);
84
85 SumofSub(0,0,sum,M,w);
86
87 return 0;
88 }