拆分自然数BFS

标签：数组 int 自然数 样例 dfs BFS 拆分

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

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1

7=1+1+1+1+1+2

7=1+1+1+1+3

7=1+1+1+2+2

7=1+1+1+4

7=1+1+2+3

7=1+1+5

7=1+2+2+2

7=1+2+4

7=1+3+3

7=1+6

7=2+2+3

7=2+5

7=3+4

输入

输入自然数n

输出

输出拆分的方案。

样例输入 Copy

7

样例输出 Copy

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

思路：dfs的变形。注意点有：1.不需要有bool类型的vis状态数组标记，观察到样例中的数组有重复项，所以不需要状态数组；2.dfs带入的参数有两个，大多数dfs的参数只有层数一个变量，但此题的变量有两个，分别为n和s，每次递归dfs(n-i,s+1),同时巧妙地找到终止条件，即s==0；3.样例中没有拆分成单独一个数，即不变的情况，因此要把此情况筛除。下面附上我的代码：

1. #include <bits/stdc++.h>  
2. #include <iostream>  
3. using namespace std;  
4. int n;  
5. const int N=15;  
6. int a[N];  
7. bool vis[N];  
8. void dfs(int n,int s){  
9.     if(n==0){  
10.         if(s<=2)return;  
11.         for(int i=1;i<s-1;i++)  
12.         cout<<a[i]<<"+";  
13.         cout<<a[s-1]<<endl;  
14.         return ;  
15.     }  
16.     for(int i=1;i<=n;i++){  
17.         if(i<a[s-1])continue;  
18.         a[s]=i;  
19.         dfs(n-i,s+1);  
20.     }  
21. }  
22. int main()  
23. {  
24.     cin>>n;  
25.     dfs(n,1);  
26.     return 0;  
27. }  

标签：数组,int,自然数,样例,dfs,BFS,拆分
From： https://www.cnblogs.com/saulgoodman1/p/17003220.html