题目 3034: 自然数的拆分

算法介绍：

        本题使用的算法为深度优先搜索算法（Depth-First-Search，DFS），该算法所遵循的策略如同名字一样，讲究一个“深”字，就是尽可能深的去搜锁所有的节点，直到把所有的节点都访问完，他的特点就是一条路走到黑。同时该算法在各大算法比赛中也经常会考到，出题率极其的高，建议读者在看完本题解后，继续查阅其他资料深入学习。

算法思想：

深度优先搜索是一个递归的过程。

1. 首先选定一个出发点，按照一种规则向下访问其他没有被访问的节点
   

2. 如果不能继续向下进行，则返回上一个节点，再继续向下进行。

3. 如果退回到下一个节点后仍不能继续进行，则继续返回上一个节点

4. 重复以上过程，直到所有的节点都被访问完毕结束。

核心代码：

该程序的核心代码如下，详细解释已经在注释中给出

//深度优先搜索算法核心部分 
void dfs(int sum,int num) //sum保存已经找到的数的和 ，num表示当前找到了多少个数 
{
    if(sum>n) //sum已经大于n时，直接结束，此时是无效的 
    {
        return;
    }
    else if(sum==n&&num!=1)  //当sum=n且num不为1时，说明已经找到了一种正确的拆分方法 
    {
        cout<<n<<"="<<d[0];
        for(int i=1;i<num;i++)
        {
            cout<<"+"<<d[i];
        }
        cout<<endl;
    }
    else  //当不满足以上两个条件时，继续向下搜其他的节点 
    {
        for(int i=1;i<=n-sum;i++)
        {
            //防止越界 
            if(num==0)   
            {
                d[num]=i;
                dfs(sum+i,num+1);
            }
            else
            {
                /*
                如果当前是第一次进入搜索，则num=0，此时d[num-1]就会越界，
                因此设置上一个if语句，以防越界访问
                */
                if(i>=d[num-1])
                {
                    d[num]=i;
                    dfs(sum+i,num+1);
                }
            }
        }
    }
}

参考代码:

#include<bits/stdc++.h>
 
using namespace std;
 
int n;  //定义一个你，代表输入的数字 
int d[9999];  //保存能够求和得到n的数 
 
 
//深度优先搜索算法核心部分 
void dfs(int sum,int num) //sum保存已经找到的数的和 ，num表示当前找到了多少个数 
{
    if(sum>n) //sum已经大于n时，直接结束，此时是无效的 
    {
        return;
    }
    else if(sum==n&&num!=1)  //当sum=n且num不为1时，说明已经找到了一种正确的拆分方法 
    {
        cout<<n<<"="<<d[0];
        for(int i=1;i<num;i++)
        {
            cout<<"+"<<d[i];
        }
        cout<<endl;
    }
    else  //当不满足以上两个条件时，继续向下搜其他的节点 
    {
        for(int i=1;i<=n-sum;i++)
        {
            //防止越界 
            if(num==0)   
            {
                d[num]=i;
                dfs(sum+i,num+1);
            }
            else
            {
                /*
                如果当前是第一次进入搜索，则num=0，此时d[num-1]就会越界，
                因此设置上一个if语句，以防越界访问
                */
                if(i>=d[num-1])
                {
                    d[num]=i;
                    dfs(sum+i,num+1);
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    dfs(0,0);  
    return 0;
}