思路:
重复的子问题:每一次车进站可以选择 出 还是 不出!
解决重复子问题:动规 or 深搜
此题 输出具体 方案,显然动规不符合
因此选择深搜
注意:除了维护数组,还需要维护一个栈结构!!!!
代码:
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int N;//火车数量
vector<vector<int>>result;
vector<int>path;
stack<int>s;
void dfs(vector<int>&ans,int x){
if(x==ans.size()&&s.empty()){
result.push_back(path);
return;
}
if(x<ans.size()){//放入栈中
s.push(ans[x]);
dfs(ans,x+1);
s.pop();
}
if(!s.empty()){//弹出栈 ,输出到数组中
int num=s.top();
path.push_back(num);
s.pop();
dfs(ans,x);
s.push(num);
path.pop_back();
}
return;
}
int main(){
cin>>N;
vector<int>ans(N);
for(int i=0;i<N;i++)
cin>>ans[i];
dfs(ans,0);
sort(result.begin(),result.end());//结果按照字典序排序
for(int i=0;i<result.size();i++){
for(int j=0;j<result[i].size();j++){
cout<<result[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
深搜问题,直接把两种情况写出来,只要满足相应的条件即可。