数组部分之和问题

「爱情、让人受尽委屈。」 2022-12-27 04:59 146阅读 0赞

### [数组部分之和问题][Link 1] ###

一个集合x有都不相同的n个元素，使用这个集合中的不定个数的元素，组成一个和为s的序列，求出所有符合的序列，元素可以重复使用，只要元素的个数相同不考虑顺序。

比如集合是x=\{2,3,4,5,7\}; n=5, s=12可以得出以下的序列：

2       2       2       2       2       2  
2       2       2       2       4  
2       2       2       3       3  
2       2       3       5  
2       2       4       4  
2       3       3       4  
2       3       7  
2       5       5  
3       3       3       3  
3       4       5  
4       4       4  
5       7

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  \#include <iostream>     
2.  \#include <vector>     
3.  **using** **namespace** std;    
4.  **int** PushVector(**int** \*x,**int** n,**int** s,vector<**int**> &tablelist,**int** Position)    
5.  \{    
6.      **if**(s<0)    
7.      \{    
8.          tablelist.clear();    
9.          **return** 0;    
10.     \}    
11.     **else** **if**(s==0)    
12.     \{    
13.         **for**(**int** i=0;i<tablelist.size();i++)    
14.         \{    
15.             cout<<tablelist\[i\]<<"\\t";    
16.         \}    
17.         cout<<"\\n";    
18.              
19.         **return** 0;    
20.     \}    
21.     **else** **if**(s>0)    
22.     \{    
23.         **for**(**int** i=Position;i<n;i++)    
24.         \{    
25.             vector<**int**> newtablelist;    
26.             **for** (**int** j=0;j<tablelist.size();j++)    
27.             \{    
28.                 newtablelist.push\_back(tablelist\[j\]);    
29.             \}    
30.             newtablelist.push\_back(x\[i\]);    
31.             **int** news = s-x\[i\];    
32.             //cout<<i<<","<<news<<"\\n";     
33.             PushVector(x,n,news,newtablelist,i);    
34.         \}    
35.      
36.      
37.     \}    
38.     **else**   
39.     \{    
40.      
41.      
42.     \}    
43.     **return** 0;    
44. \}    
45.      
46.      
47. /\* run this program using the console pauser or add your own getch, system("pause") or input loop \*/   
48. **int** FindResult(**int** \* x,**int** n,**int** s)    
49. \{    
50.     vector<**int**> tablelist;    
51.     tablelist.clear();    
52.     PushVector(x,n,s,tablelist,0);    
53.     **return** 0;    
54. \}    
55.      
56.      
57.      
58.      
59. **int** main(**int** argc, **char**\*\* argv)     
60. \{    
61.     **int** x\[\]= \{2,3,4,5,7\};    
62.     **int** n =5;    
63.     **int** s=12;    
64.     FindResult(x,n,s);    
65.     system("pause");    
66.     **return** 0;    
67. \}    
68.    
69. \#include <iostream>  
70. \#include <vector>  
71. **using** **namespace** std;  
72. **int** PushVector(**int** \*x,**int** n,**int** s,vector<**int**> &tablelist,**int** Position)  
73. \{  
74.     **if**(s<0)  
75.     \{  
76.         tablelist.clear();  
77.         **return** 0;  
78.     \}  
79.     **else** **if**(s==0)  
80.     \{  
81.         **for**(**int** i=0;i<tablelist.size();i++)  
82.         \{  
83.             cout<<tablelist\[i\]<<"\\t";  
84.         \}  
85.         cout<<"\\n";  
86.            
87.         **return** 0;  
88.     \}  
89.     **else** **if**(s>0)  
90.     \{  
91.         **for**(**int** i=Position;i<n;i++)  
92.         \{  
93.             vector<**int**> newtablelist;  
94.             **for** (**int** j=0;j<tablelist.size();j++)  
95.             \{  
96.                 newtablelist.push\_back(tablelist\[j\]);  
97.             \}  
98.             newtablelist.push\_back(x\[i\]);  
99.             **int** news = s-x\[i\];  
100.             //cout<<i<<","<<news<<"\\n";  
101.             PushVector(x,n,news,newtablelist,i);  
102.         \}  
103.    
104.    
105.     \}  
106.     **else**  
107.     \{  
108.    
109.    
110.     \}  
111.     **return** 0;  
112. \}  
113.    
114.    
115. /\* run this program using the console pauser or add your own getch, system("pause") or input loop \*/  
116. **int** FindResult(**int** \* x,**int** n,**int** s)  
117. \{  
118.     vector<**int**> tablelist;  
119.     tablelist.clear();  
120.     PushVector(x,n,s,tablelist,0);  
121.     **return** 0;  
122. \}  
123.    
124.    
125.    
126.    
127. **int** main(**int** argc, **char**\*\* argv)   
128. \{  
129.     **int** x\[\]= \{2,3,4,5,7\};  
130.     **int** n =5;  
131.     **int** s=12;  
132.     FindResult(x,n,s);  
133.     system("pause");  
134.     **return** 0;  
135. \}

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <stdlib.h>  
3.  \#include <assert.h>  
4.  \#include <string.h>  
5.  \#include <memory.h>  
6.  \#define \_DEBUG 1  
7.  \#define MAXM 20  
8.  \#define MAXN 10  
9.  **int** arr\[MAXN\];//数数组  
10. **bool** path\[MAXN\]\[MAXM+1\];//路线  
11. **bool** hashtable\[MAXM+1\];//是否存在  
12. **int** c;//记录打印队列大小  
13. **int** v\[MAXM+1\];//打印队列，数组大小最大为MAXN+1，此时每个数为1  
14.   
15. **void** printPath(**int** i,**int** j,**int** c)\{  
16.     **if**(path\[i\]\[j\] &&j-arr\[i\]==0)\{ //第一个点  
17.         printf("%d ",arr\[i\]);  
18.         **for**(**int** t=c-1;t>0;t--)\{  
19.             printf("%d ",v\[t\]);  
20.         \}  
21.         printf("%d\\n",v\[0\]);  
22.         **return**;  
23.     \}  
24.     assert(path\[i\]\[j\]);  
25.     v\[c++\]=arr\[i\];//将元素加入到打印队列中  
26.     **for**(**int** k=1;k<=i;k++)\{  
27.         **if**(path\[k\]\[j-arr\[i\]\])  
28.             printPath(k,j-arr\[i\],c);          
29.     \}  
30.     c--;//将元素从打印队列中删除  
31. \}  
32.   
33. **void** solve(**int** size,**int** m)\{ //size表示数组的大小,从1开始  
34.     **int** i,j;  
35.     //初始化  
36.     memset(path,**false**,**sizeof**(path));  
37.     hashtable\[0\]=**true**;    
38.     **for**(i=1;i<=size;i++)\{  
39.         **for**(j=arr\[i\];j<=m;j++)\{  
40.             **if**(hashtable\[j-arr\[i\]\])\{  
41.                 hashtable\[j\]=**true**;  
42.                 path\[i\]\[j\]=**true**;  
43.             \}  
44.         \}  
45.     \}  
46.     **for**(i=1;i<=size;i++)\{  
47.         **if**(path\[i\]\[m\])\{  
48.             printPath(i,m,0);  
49.         \}  
50.     \}  
51. \}  
52. **int** main()\{  
53. \#if \_DEBUG==1  
54.     freopen("interview.in","r",stdin);  
55. \#endif  
56.   
57.     **int** n,m;  
58.     **int** i,j;  
59.   
60.     scanf("%d %d",&n,&m);  
61.     **for**(i=1;i<=n;i++)\{  
62.         scanf("%d",&arr\[i\]);  
63.     \}  
64.     solve(n,m);  
65.     **return** 0;  
66. \}

[Link 1]: http://blog.csdn.net/hwltony/article/details/10107573
[view plain]: http://blog.csdn.net/hwltony/article/details/10107573#