Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
毕竟初学DFS#include <iomanip> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <functional> #include <vector> #include <cmath> #include <string> #include <stack> #include <queue> #include <list> using namespace std; int t,n,a[20],temp[20]; //temp数组是为了存放对应答案 bool flag; void DFS(int sum,int pos,int cnt) { if(sum==t){ printf("%d",temp[0]); for(int i=1;i<cnt;i++) printf("+%d",temp[i]); printf("\n"); flag=true; //判断是否有解 }else{ for(int j=pos;j<n;j++){ if(j==pos || a[j]!=a[j-1]){ //此处 a[j]!=a[j-1]是为了避免重复 temp[cnt]=a[j]; DFS(sum+a[j],j+1,cnt+1); //总是写不好一个递归 } } } } int main() { while(scanf("%d %d",&t,&n)==2) { if(t==0 && n==0) break; for(int i=0;i<n;i++) scanf("%d",&a[i]); flag=false; printf("Sums of %d:\n",t); DFS(0,0,0); if(!flag) printf("NONE\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator