欢迎各位赏脸来看本蒟蒻的题解 保姆级教程（不是）

一眼dfs 但是可能会遇到重复加的问题 导致答案错误

其实只要 思考一下dfs递归的本质 就会发现 只需要加一个 特判就可以完美的去重

还有一个小技巧 如果从n开始 加一个数就减一个 就会让我们后面的判定简单很多

话不多说 直接上代码

Code：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long //个人习惯 被坑多了就习惯了
using namespace std;
int n;
int a[10010];
void dfs(int x , int now , int st) //x记录每次加的数 ， now记录当前还需要加的数 ， st记录数组下标 用于递归完后输出答案；
{
    if (now == 0)
    { 
        printf("%d=", n);      // =的位置需要注意 不要放在for里面了
        for (int i = 1 ; i < st - 1 ; i ++ )
        {
            printf ("%d+" , a[i]);       
        }
        printf("%d\n" , a[st - 1]);  //最后一个需要单独挑出来 不然会多出+号
    }
    for (int i = 1 ; i < n ; i ++ )
    {
        if (now - i >= 0 && i >= a[st - 1])    //重点 i >= a[st - 1] 特判处理上一个状态的数字 必须满足当前加的数 大于等于上一个数 即可完美去重 不需要使用哈希表去重 节约时间
        {
            a[st] = i; // 记录答案
            dfs(i , now - i , st + 1);  // 递归
        }
    }
}
signed main()
{
    cin>> n;
    dfs(0 , n , 1);   // 从n开始 记录为第一个位置
    return 0 ;
}