alan23273850 的刷題筆記
a144: 整數分拆
Tags: partition
出處：https://zerojudge.tw/ShowProblem?problemid=a144
提交：https://zerojudge.tw/Submissions?problemid=a144&account=allllllan123456
問題：對於一個小於 100 的正整數，請以字典順序由大到小印出它所有的分拆情況。
解法：只是 DFS 的一個應用而已。
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100], arrL;
5
6void dfs(int n) {
7 if (!n) {
8 for (int i=0; i<arrL; i++) {
9 if (i) cout << ' ';
10 cout << arr[i];
11 }
12 cout << '\n'; return;
13 }
14 for (int i= !arrL ? n : min(n, arr[arrL-1]); i>0; i--)
15 arr[arrL++] = i,
16 dfs(n-i),
17 arrL--;
18}
19
20int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
21 int n;
22 while (cin >> n) arrL = 0, dfs(n);
23 return 0;
24}