【一級講解】拆分自然數——經典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');
}