【一级讲解】拆分自然数——经典DFS例题

题目：

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

示例输入

6
           

示例输出

[Situation 1]:1 1 1 1 1 1
[Situation 2]:1 1 1 1 2
[Situation 3]:1 1 1 3
[Situation 4]:1 1 2 2
[Situation 5]:1 1 4
[Situation 6]:1 2 3
[Situation 7]:1 5
[Situation 8]:2 2 2
[Situation 9]:2 4
[Situation 10]:3 3
The total number of disassemble is 10
           

问题分析：

这道题目稍微有一点点进阶，在读完题目，尤其是看完示例后，你会发现这道题目与之前题目最大的不同点一在于答案长度的不确定，二在于可以重复使用自然数（元素）。

但其实这两个问题只要稍微修改一下DFS中的判断条件就好了~

同样的，我们拿出我总结的模板来套一套

DFS模板
int dfs ( int n )
{
	for ( 遍历所有可能的情况 )
		if ( 符合判断条件 )
			{
				保存结果
				if ( 符合输出最终解/边界条件 )
					输出操作;
				else 
					继续深度搜索 dfs ( n+1 );
				回溯复原; 
			} 		 
} 
           

①很明显这里的所有可能就是：从1、2、3、…、一直到newN

可能很多人会很疑问，到底什么是newN呢？

别急，等我慢慢来解释。

也许你一下子不知道拆分6的情况有多少种，那也许5的难度会更低一点，同理，4的难度会比5低，3的难度会比4低，那我们这里就从最小自然数（除0外）的1开始遍历，

每次找到符合条件的数就将其记录入“答案队列”然后将

n-符合条件的数
           

并更新为newN。这样子每一轮我们符合条件的数都要符合

i<=newN
           

至于初始条件，我们选择

i=ans[k-1]
           

这是因为我们每次选数字都要大于或等于上一次选的数字，那么这么写后自然而然就要关注临界情况，即ans[1]的情况，需要预先赋值为1.

②是否符合判断条件：

这里就要解决如何可以重复使用自然数（元素）。

很简单，不处理就好了。

？？？也许你会有点懵，但回想一下，前面几道题目我们是不是都用bool数组来mark一下防止重复使用，这里题目没有要求，自然不处理就好了。

③保存结果：

很经典的两部分可以去掉第二部分，只留下一部分将这个数收入“答案队列”中等待“全员到齐”输出即可

④符合输出最终解/边界条件：

解决第二个问题答案长度的不确定，之前我们都是等待“全员到齐”输出即可，但这里怎么判断全员到齐了呢？那就是newN=0咯

⑤输出操作：

很经典的单独定义一个输出函数以专门的格式输出

⑥回溯复原：

重新加回上一轮符合条件的数，等待下一次搜索

其实我第一次写的时候因为两个细节错了，这里贴上我的错误代码，并分析错误原因。

#include<bits/stdc++.h>
using namespace std;

int ans[100001]={1},n,cnt;
void dfs(int,int);
void print(int);

int main()
{
    cout << "Please enter [n]" << endl;
    cin >> n;
    dfs(n,1);
    cout << "The total number of disassemble is " << cnt;
}

void dfs(int newN, int k)
{
/********************************************
    for ( int i=ans[k-1]; i<newN; ++i )
    {
        if ( i<newN )
        {
********************************************/
            ans[k] = i;
            newN-=i;
            if (newN==0)   
                print(k);
            else
                dfs(newN,k+1);
            newN+=i;
        }
    }
}

void print(int k)
{
    cnt++;
    cout << "[Situation " << cnt << "]:" << ans[1];
    for ( int i=2; i<=k; ++i )
        cout << " " << ans[i];
    putchar('\n');
}
           

我已经标记了错误地点，你能否发现错误呢？

对了，就是条件的错误，for循环应该是<=不然永远都不会符合输出条件。

第二个错误是if的判断应该是if ( i<n )

因为我们最后是不需要n这个数的，因为单独一个n其实是没有“拆分”的。

代码：

#include<bits/stdc++.h>
using namespace std;

int ans[100001]={1},n,cnt;
void dfs(int,int);
void print(int);

int main()
{
    cout << "Please enter [n]" << endl;
    cin >> n;
    dfs(n,1);
    cout << "The total number of disassemble is " << cnt;
}

void dfs(int newN, int k)
{
    for ( int i=ans[k-1]; i<=newN; ++i )
    {
        if ( i<n )
        {
            ans[k] = i;
            newN-=i;
            if (newN==0)   
                print(k);
            else
                dfs(newN,k+1);
            newN+=i;
        }
    }
}

void print(int k)
{
    cnt++;
    cout << "[Situation " << cnt << "]:" << ans[1];
    for ( int i=2; i<=k; ++i )
        cout << " " << ans[i];
    putchar('\n');
}