思路
定义三个容器,st1表示输出的顺序,st2维护栈,st3代表还未进栈的元素
操作1:取出栈顶元素加入到st1后,且只在栈非空时进行
操作2:取出st3为入栈元素入栈,且只在st3容器中的元素个数不为0时进行
注意:应保证先进行操作1,输出的才是字典序
dfs
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int n;
vector<int> st1;
stack<int> st2;
int st3 = 1;
int cnt = 20;
void dfs(){
if(cnt == 0) return ;
if(st1.size() == n){
cnt --;
for(auto i : st1) printf("%d",i);
printf("\n");
return ;
}
if(st2.size()){ //操作1:取出栈顶元素加入到st1后,且只在栈非空时进行
st1.push_back(st2.top());
st2.pop();
dfs();
st2.push(st1.back()); //状态还原
st1.pop_back();
}
if(st3 <= n){ //操作2:取出st3为入栈元素入栈,且只在st3容器中的元素个数不为0时进行
st2.push(st3);
st3 ++;
dfs();
st2.pop();//状态还原
st3 --;
}
}
int main(){
cin >> n;
dfs();
return 0;
}
大佬牛
讲的很好,赞