Sum It Up---poj1564（dfs）

题目链接：http://poj.org/problem?id=1564

给出m个数，求出和为n的组合方式；并按从大到小的顺序输出；

简单的dfs但是看了代码才会；

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, flag;

int a[], b[];

int cmp(int a, int b)

{

    return a>b;

}

void dfs(int pos, int len, int sum)///pos代表位置；

{

    if(sum==n)

    {

        flag=;

        printf("%d", b[]);

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

            printf("+%d", b[i]);

        printf("\n");

        return ;

    }

    for(int i=pos; i<m; i++)

    {

        if(sum+a[i]<=n)

        {

            b[len]=a[i];

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

            while(i+<m && a[i]==a[i+])i++;///去重；

        }

    }

}

int main()

{

    while(scanf("%d %d", &n, &m), m+n)

    {

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

            scanf("%d", &a[i]);

        sort(a, a+m, cmp);

        flag = ;

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

        dfs(, , );

        if(flag==)

            printf("NONE\n");

    }

    return ;

}