49 lines
1.2 KiB
C++
49 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
//哪个数字
|
||
int n;
|
||
//全局路径（需要回溯）
|
||
vector<int> path;
|
||
|
||
//输出
|
||
void print() {
|
||
//划分成两部分，最后一部分不在尾巴上加+号！
|
||
for (int i = 0; i < path.size() - 1; i++) cout << path[i] << "+";
|
||
cout << path[path.size() - 1] << endl;
|
||
}
|
||
|
||
//深度优先搜索
|
||
void dfs(int x, int sum) {
|
||
//终止条件
|
||
if (path.size() > 1 && n == sum) {//需要把一个数字描述成2个及2个以上数字的和，
|
||
// 自已描述自己不行，就是path.size()>1
|
||
print();
|
||
return;
|
||
}
|
||
//本轮添加上什么样的数字：可以是1，2，3，...,n
|
||
for (int i = 1; i <= x; i++) {
|
||
//1、路径空的时候可以放
|
||
//2、路径不空，同时，当前要加入的数字比尾巴上的数字要大，也可以放
|
||
if (path.empty() || i >= path[path.size() - 1]) {
|
||
//加入
|
||
path.push_back(i);
|
||
//递归
|
||
dfs(x - i, sum + i);
|
||
//回溯
|
||
path.pop_back();
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n;
|
||
//深度优先搜索
|
||
dfs(n, 0);
|
||
return 0;
|
||
}
|
||
|
||
|
||
|