自然数拆分（深搜）

/*
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3104
回溯法

*/

#include <iostream>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int n;
using namespace std;
int a[36];
int vis[36][36];
void dfs(int cur,int sum)
{

    if(sum==0&&cur>2)
    {
        printf("%d=%d",n,a[1]);
        for(int i=2; i<cur; i++)
            printf("+%d",a[i]);
        printf("
");
        return;
    }

    for(int i=1; i<=sum; i++)
    {
        if( i>=a[cur-1])
        {

            a[cur]=i;
            dfs(cur+1,sum-i);//每用掉一个数后，就将总值减去这个数，然后在剩下的数中在进行分割；
                                        //不用做标记因为在同一组数据中可以重复使用数据；
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        dfs(1,n);
    }
    return 0;
}