一个DFS题目,应该说加深了对DFS的理解吧。以前对DFS的理解云里雾里的,今天一看,觉得数组的数值不会被改变吗怎么会输出正确的结果?我是看漏了DFS最重要的一点“return”!他找到正确答案或者超出边界是要return的!!!这样数组就会重新赋值,恍然大悟啊!!!

        题意:给一行数,第一个代表总和,第二个代表接下来有n个数,要求你从这N个数里面找出所有加起来等于和的案例,不能重复,从大到小输出。这个结合案例就能看懂。


题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1258


代码:

Memory: 252 KB
Time: 0 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=13;
int sum, n, i, flag;
int res[maxn], ans[maxn];
void dfs(int add, int index, int cur)
{
    ///add是当前的和,index是原始搜索值的下标,cur是结果数组下标
    if(add==sum)
    {
        flag=0;
        cout<<ans[0];
        for(i=1;i<cur;i++)cout<<"+"<<ans[i];
        cout<<endl;
        return;
    }
    for(int j=index;j<n;j++)
    {
        if(j==index||res[j]!=res[j-1])
        {///保证不会重复
            ans[cur]=res[j];
            dfs(add+res[j],j+1,cur+1);
        }
    }
}
int main()
{
    while(cin>>sum>>n && sum+n)
    {
        flag=1;
        for(i=0;i<n;i++)cin>>res[i];
        printf("Sums of %d:\n", sum);
        dfs(0, 0, 0);
        if(flag)printf("NONE\n");
    }
    return 0;
}