整数划分，并按字典序（递减）输出

 1 #include <iostream>
 2 #include <deque>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int sum = 0, nn = 0, ans = 0;
 7 deque<int> dq;    // 便于删除插入遍历
 8 
 9 void dfs(int n) {    // 深度优先搜索，从 nn -> 1
10     for (int i = n; i >= 1; i--) {    // 从nn往下遍历
11         dq.push_back(i);
12         sum += i;    
13         if (sum > nn) {        // 剪枝
14             sum -= i;
15             dq.pop_back();
16         }
17         else if (sum == nn) {    // 输出
18             deque<int>::iterator it;
19             for (it = dq.begin(); it != dq.end(); it++)
20                 if (it == dq.begin())
21                     cout << *it;
22                 else
23                     cout << " + " << *it;
24             cout << endl;
25             sum -= i;
26             ans++;
27             dq.pop_back();
28         } else {    // 深度搜索
29             dfs(i);
30             sum -= i;
31             dq.pop_back();
32         }
33     }
34 }
35 
36 int main() {
37     cout << "please input nn : ";
38     cin >> nn;
39     dfs(nn);
40     cout << "total = " << ans << endl;
41     return 0;
42 }