求调dfs
查看原帖
求调dfs
1035847
Tomatos03楼主2024/2/28 16:41
#include <bits/stdc++.h>
//----mxcro----------------
#define MAXN int(10)
#define BASE 121
#define endl '\n'
#define rep(i, starts, ends) for(int i = starts; i <= ends; ++i)
//----namespace------------
using namespace std;
//----struct---------------
struct node{ int x, y;};
//----constxnt-------------
const double eps = 1e-4;
//----verious-------------
int n, selected[MAXN];
set<string> st;
//----mathod-----------

void dfs(int len, int k, int curSum) {
    if (k == len + 1) {
        if (curSum != n) return;
        sort(selected + 1, selected + len + 1);
        string s = "";
        rep(i, 1, len) {
            s += to_string(selected[i]);
            if (i < len) s += "+";
        }
        st.insert(s);
        return;
    }
    rep(i, 1, n) {
        if (i + curSum > n) {
            return;
        }
        if (i + curSum == n && k != len) { 
            return;
        }
        selected[k] = i;
        dfs(len, k + 1, curSum + i);
    }
}

void solve() {
    cin >> n;
    rep(i, 2, n) {
        dfs(i, 1, 0);
    }
    vector<string> ans;
    for(string s : st) {
        ans.push_back(s);
    }
    sort(ans.begin(), ans.end());
    for(string s : ans) {
        cout << s << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    /*
    int t;
    cin >> t;
    while(t-- > 0) {
        solve();
    }
    */
    solve();
    return 0;
}
2024/2/28 16:41
加载中...