題意：給你一個數sum，然後再給你一個數n，再給你n個數，從n個數中找出一些數，讓這些數的和是n。所給的n個數是遞減的，讓輸出的結果也是按照遞減的形式輸出。
思路：由於n最大為12，所以很明顯可以暴力搜出所有的情況，然後判斷和是否為sum，如果為sum，則輸出即可。需要注意兩點的是：首先有一個去重的過程，我的處理是把合適的全部存在一個vector裡面，然後找到合適的去vector裡面逐個判斷是否和某一個重復，若都不重復，則符合題意，並且把這個也記錄到vector裡面。因為最後要從大到小輸出，所以我又用了一個結構體存下來答案，最後又對結構體排了下序，之後的就是正解了。
代碼：
[cpp]
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
struct add{
int ans[15];
int size;
}aa[100005];
int num[15],flag[15],num2[15],sum,n,numvv,numaa;
bool isok;
vector<int> vv[5005];
bool fun(int cnt){
bool is = false;
for(int i = 0; i < numvv; ++i){
is = false;
if(vv[i].size() == cnt){
for(int j = 0 ;j < vv[i].size(); ++j){
if(num2[j] != vv[i][j]){
is = true;
break;
}
}
if(!is)
return false;
}
}
return true;
}
void dfs(int begin,int id,int cnt){
if(id == cnt){
int ss = 0;
for(int i = 0; i < cnt; ++i)
ss += num2[i];
if(ss == sum && fun(cnt)){
isok = true;
aa[numaa].size = cnt;
for(int i = 0; i < cnt; ++i){
aa[numaa].ans[i] = num2[i];
}
numaa++;
for(int i = 0; i < cnt; ++i){
vv[numvv].push_back(num2[i]);
}
numvv++;
}
return;
}
for(int i = begin; i < n; ++i){
if(!flag[i]){
num2[id] = num[i];
flag[i] = true;
dfs(i,id+1,cnt);
flag[i] = false;
}
}
}
bool cmp(add a,add b){
for(int i = 0; i < 13; ++i){
if(a.ans[i] > b.ans[i])
return true;
else if(a.ans[i] < b.ans[i])
return false;
}
}
int main(){
//freopen("1.txt","r",stdin);
while(scanf("%d%d",&sum,&n) && n){
CLR(num,0);
CLR(flag,0);
CLR(vv,0);
numvv = 0;
numaa = 0;
for(int i = 0; i < n; ++i)
scanf("%d",&num[i]);
isok = false;
printf("Sums of %d:\n",sum);
for(int i = 1; i <= n; ++i){
CLR(flag,0);
CLR(num2,0);
dfs(0,0,i);
}
if(!isok)
printf("NONE\n");
else{ www.2cto.com
sort(aa,aa+numaa,cmp);
for(int i = 0; i < numaa; ++i){
int len = aa[i].size;
for(int j = 0; j < aa[i].size - 1; ++j){
printf("%d+",aa[i].ans[j]);
}
printf("%d\n",aa[i].ans[len-1]);
}
}
}
return 0;
}
作者：wmn_wmn
