poj 1564 Sum It Up | zoj 1711 | hdu 1548 (dfs + 剪枝 or 判重) (二)
if(sum-a[i]<0||(k>0&&a[i]>p[k-1])) continue;
vis[i] = 1;
p[k] = a[i];
dfs(k+1,sum-a[i]);
vis[i] = 0;
while(i+1
}
}
int main() {
int i;
while(scanf("%d%d",&t,&n),t+n) {
for(i=0; i
i = 0;
while(it) i++;
printf("Sums of %d:\n",t);
flag = 0;
memset(vis,0,sizeof(vis));
dfs(i,t);
if(!flag) printf("NONE\n");
}
return 0;
}
code2:(用 set 去重：在POJ和ZOJ上提交全挂，不过hdu上能AC，呃呃呃~)
HDU:Accepted 1258 0MS 340K 1286 B G++
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N 20
int t, n;
int a[N];
int list[N];
bool vis[N];
set s;
bool flag;
void dfs(int k, int sum) {
int i;
if(k>=n || sum<0) return;
if(sum==0) {
string str;
for(i=0; i
str +=(list[i]/10) +'0';
str +=(list[i]%10) +'0';
}
if(s.find(str)==s.end()) {
s.insert(str);
flag = 1;
for(i=0; i
printf("%d+",list[i]);
printf("%d\n",list[i]);
}
return ;
}
for(i=k; i
if(!vis[i]&&(k==0||a[i]<=list[k-1])) {
vis[i] = 1;
list[k] = a[i];
dfs(k+1,sum-a[i]);
vis[i] = 0;
}
}
int main() {
int i;
while(scanf("%d%d",&t,&n),t+n) {
for(i=0; i
scanf("%d",&a[i]);
}
memset(vis,0,sizeof(vis));
printf("Sums of %d:\n",t);
flag = false;
s.clear();
dfs(0,t);
if(!flag) printf("NONE\n");
}
return 0;
}
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N 20
int t, n;
int a[N];
int list[N];
bool vis[N];
set s;
bool flag;
void dfs(int k, int sum) {
int i;
if(k>=n || sum<0) return;
if(sum==0) {
string str;
for(i=0; i
str +=(list[i]/10) +'0';
str +=(list[i]%10) +'0';
}
if(s.find(str)==s.end()) {
s.insert(str);
flag = 1;
for(i=0; i
printf("%d+",list[i]);
printf("%d\n",list[i]);
}
return ;
}
for(i=k; i
if(!vis[i]&&(k==0||a[i]<=list[k-1])) {
vis[i] = 1;
list[k] = a[i];
dfs(k+1,sum-a[i]);
vis[i] = 0;
}
}
int main() {
int i;
while(scanf("%d%d",&t,&n),t+n) {
for(i=0; i
scanf("%d",&a[i]);
}
memset(vis,0,sizeof(vis));
printf("Sums of %d:\n",t);
flag = false;
s.clear();
dfs(0,t);
if(!flag) printf("NONE\n");
}
return 0;
}