n个数，入栈出栈，所有情况

n个数，入栈出栈，所有情况

int count = 0;void print(vector& trace, vector& push_order) { int i = 0; stackstk; for (auto n : trace) { if (n == 1) { stk.push(push_order[i++]); } else { int num = stk-(); stk.pop(); cout << num << " "; } } cout << endl; ::count++;}void backtrack(vector& trace, vector& push_order, int left) { // trace:{0 出栈,1 入栈}, push_order:操作的数字, left:push比pop多的次数，也就是栈中还有几个数 // left记录前缀序列中1的个数，每当trace中push一个0，就减一 if (trace.size() == 2 * push_order.size()) { // 递归出口 if (left == 0) // 只有left=0，才能使得0的数量==1的数量，才是合法的。 print(trace, push_order); return; } // 做选择 if (left > 0) { // 如果left>0，则可以push 0进去 ,同时 left-1 trace.push_back(0); backtrack(trace, push_order, left - 1); // 撤销选择 trace.pop_back(); } trace.push_back(1); backtrack(trace, push_order, left + 1); trace.pop_back();}int main() { vector push_order = { 1,2,3,4 }; vectortrace; backtrack(trace, push_order, 0); cout << ::count << endl; const int maxI = 4; function&, list&, int)> fun = [&](stack st, list out, int index) { if (out.size() == maxI) { for_each(begin(out), end(out), [](int x) {cout << x << " "; }), cout << endl; return; } if (st.size() > 0) { int t = st-(); st.pop(); out.push_back(t); fun(st, out, index); st.push(t); out.pop_back(); } if (index <= maxI) { st.push(index++); fun(st, out, index); } }; stackst; list out; fun(st, out, 1);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。