递归与非递归的方法。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct state {
    int state, i;
};

//递归
void solve(vector<int> &v, const int n){
    // 0
    if(v.size() == n) {
        for(int i = 0; i < v.size(); ++i) {
            printf("%d ", v[i]);
        }
        cout << endl;
        return;
    }
    for(int i = 0; i < n; ++i) {
        bool flag = true;
        for(int j = 0; j < v.size(); ++j) {
            if(v[j] == i + 1) {
                flag = false;
                break;
            }
        }
        if(flag) {
            v.push_back(i + 1);
            solve(v, n);
            // 1
            v.pop_back();
        }
    }
    return;
}

//非递归
void nonSolve(const int n) {

    stack<state> stk;
    stk.push({0, 0});
    vector<int> v;
    while(stk.size()) {

        auto t = stk.top(); stk.pop();
        //cout << "stack: " << t.state << ", " << t.i << ": " << v.size() << ", " << stk.size() << endl;
        if(0 == t.state) {
            if(v.size() == n) {
                for(int i = 0; i < v.size(); ++i) {
                    printf("%d ", v[i]);
                }
                cout << endl;
                continue;
            }
            if(t.i < n) {
                bool flag = true;
                for(int j = 0; j < v.size(); ++j) {
                    if(v[j] == t.i + 1) {
                        flag = false;
                        break;
                    }
                }
                //递归方法中的for循环，要保存当前的状态。
                t.i += 1;
                stk.push(t);
                if(flag) {
                    v.push_back(t.i);
                    t.state = 1;
                    stk.push(t);
                    stk.push({0, 0});
                }
            }
        } else {
            v.pop_back();
        }
    }
}


int main() {
    int n;
    while(scanf("%d", &n) != EOF){
        vector<int> v;
        //solve(v, n);
        nonSolve(n);
    }
}