hdu1258（DFS）

题目：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");
        }
    }
}