题目:https://acm.hdu.edu.cn/showproblem.php?pid=1258
思路:根据题意: 输出应该是从大到小的,所以先排序
1. 将数组排序
2. 写 DFS()模板
3. 参数:int sum ; //当前已经组成的和,
Int x; // 当前所搜索的元素,(数组下标)
返回值:void // 当当前和sum = t时,输出结果
4. 每次判断当前元素,两种情况:a[x]加入sum, a[x]不加入sum中
5. 输出结果时要判断此结果是否已经输出过了,因为全是数字,我这里将结果保存成字符串,如结果是 2+3+4; 则保存成字符串234存入set集合中,
输出之前先判断是否已存在set中,不存在则输出;
#include<iostream> #include<stdio.h> #include<string> #include<stdlib.h> #include<algorithm> #include<set> using namespace std; int a[15],p[15],m[15],n,t,flag;// a[] 存元素, m[]存输出元素,p[]中间临时存放访问元素 bool vis[15]; //标记元素是否已经访问 set<string>st;//存放输出过的结果 void dfs(int sum,int x) { int i,j; if(sum==t){//sum结果已经凑够t flag=1; string s; //结果转化成字符串 for(i=n-1,j=0;i>=0;i--){ if(p[i]!=99999){ m[j++] = p[i]; s += char(p[i]+'0'); } }s+='\0'; if(st.find(s)==st.end()){ //如果 set中找不到s,说明该结果没有输出过 st.insert(s); //加入到集合 for(i=0;i<j-1;i++){ printf("%d+",m[i]); }printf("%d\n",m[j-1]); } return ; } if(x<0) return; vis[x] = 1; p[x] = a[x]; //情况1. 需要该元素,:标记该元素为已访问,并加入p[] dfs(sum+a[x],x-1); //a[x]加入sum,并判断下一个元素 vis[x]=0; p[x] = 99999; //情况2. 不需要该元素,:标记该元素为未访问,并从p[]中删除 dfs(sum,x-1); //a[x]不加入sum,并判断下一个元素 } int main() { int i; while(~scanf("%d%d",&t,&n),n) { //3个数组的初始化 for(i=0;i<n;i++){ scanf("%d",&a[i]); p[i] = 99999; vis[i] = 0; } sort(a,a+n); //排序 printf("Sums of %d:\n",t); flag=0; dfs(0,n-1); //从大的开始搜索 ,所以下标从n-1 if(flag==0) puts("NONE"); } return 0; }
java代码:
import java.util.*; public class Main { static Set<String> set = new HashSet<String>(); static int n,t,flag; static int [] a = new int [15]; static int [] p = new int [15]; static int [] m = new int [15]; static boolean vis[] = new boolean [15]; static void dfs(int sum,int x) { if(sum==t){ String s = ""; int j = 0; for(int i=n-1;i>=0;i--){ if(p[i]!=99999){ m[j++] = p[i]; s += p[i]; } } if(!set.contains(s)){ set.add(s); int i; flag = 1; for(i=0;i<j-1;i++){ System.out.print(m[i]+"+"); }System.out.println(m[j-1]); } return ; } if(x<0) return; vis[x] = true; p[x] = a[x]; dfs(sum + a[x],x-1); vis[x] = false; p[x] = 99999; dfs(sum,x-1); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext()){ t = cin.nextInt(); n = cin.nextInt(); if(n==0) break; for(int i=0;i<n;i++){ a[i] = cin.nextInt(); p[i] = 99999; vis[i] = false; } Arrays.sort(a, 0, n); //数组排序算法 set.clear(); flag = 0; System.out.println("Sums of "+t+":"); dfs(0,n-1); if(flag==0)System.out.println("NONE"); } } }