(vector)与栈(stack)+dfs

因为要按字典序输出，所以先走第2条路，在走第1条路

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
vector<int>state1;
stack<int>state2;
int state3=1;
int n,cnt=20;   //cnt记录不超过20个
void dfs()
{
    if(!cnt)    return ;
    if(state1.size()==n)    //如果state1长度等于n
    {
        cnt--;  
        for(int i=0;i<n;i++)    //输出答案
            cout<<state1[i];
        cout<<endl;
        return ;
    }
    //走第2条路，将state2的元素放入state1的末尾
    if(state2.size())   //如果state2不为空
    {
        state1.push_back(state2.top());     //则将state2的栈顶元素放入state1的末尾，并未删除
        state2.pop();   //删除栈顶元素
        dfs();
        state2.push(state1.back());     //恢复现场，将state1的末尾元素压入state2的栈顶
        state1.pop_back();      //将state1的末尾元素删除
    }
    //走第一条路，将state1的值放入state2的栈顶中
    if(state3<=n)       //如果state3的值小于等于n
    {
        state2.push(state3);        //那么state3的值压入state2的栈顶
        state3++;   //state3的值增大
        dfs();  
        state3--;   //恢复现场，state3的值变回去
        state2.pop();   //将state2的栈顶元素弹出即删除
    }
}
int main()
{
    cin>>n;
    dfs();
    return 0;
}