简单深搜：POJ1546——Sum it up

结束了三分搜索的旅程 我开始迈入深搜的大坑。。

首先是一道比较基础的深搜题目（还是很难理解好么）

POJ 1564 SUM IT UP

大体上的思路无非是通过深搜来进行穷举、匹配

为了能更好地理解深搜 可以尝试去画一下二叉树理解一下，查看遍历的路径

代码还是百度到别人的自己再参悟- -佩服别人的功底啊

先上代码：

/*POJ 1546 Sum it up*/

# include<iostream>

# include<algorithm>

# include<cstdio>

using namespace std;

int a[], b[],t,n,sum,cnt;

bool cmp(int a, int b)

{

    return a > b;

}

void dfs(int posa,int posb,int sum)

{

    if (sum > t)

        return;

    if (sum == t)

    {

        cnt++;

        for (int i = ; i < posb; i++)

        {

            if (i == )

                cout << b[i];

            else

                cout << "+" << b[i];

        }

        cout << endl;

    }

    for (int i = posa; i < n; i++)

    {

        b[posb] = a[i];

        dfs(i + , posb + , sum + a[i]);

        while (a[i] == a[i+]&&i+<n)

            i++;//防止重复运算（剪枝）

    }

}

int main()

{

    while (cin >> t >> n)

    {

        if (t==&&n==)

            break;

        for (int i = ; i < n; i++)

            cin >> a[i];

        sort(a, a + n, cmp);//为了按照题目要求进行降序输出，先对初始数组降序排序

        printf("Sums of %d:\n", t);

        cnt = ;

        dfs(, , );

        if (!cnt)

            printf("NONE\n");

    }

    return ;

}

解释一下实现的方法。首先：数组a用来存放输入的一组数字，数组b用来暂时储存本次深搜路径生成的组合

深搜的主体部分不过多解释。。还是自己画树理解最好

一些细节：1.剪枝：在树的同一层一个数字没必要试两遍，所以如果这一层的下一个元素还是和原来一样就跳过它继续

　　　　　2.降序：题目要求了降序输出。那么在深搜前直接现对数组a降序排列即可