输入一个序列,返回所有可能的出栈序列
oh my god,我终于相信了墨菲定律
回溯法
从给定的字符串str中选取字符,并以不同的顺序压入栈中,然后依次从栈中弹出字符到临时字符串tem中,直到tem与str完全相同为止。每次当tem与str长度相同时(所有元素的一个排列),就将tem作为一个可能的序列添加到结果集res中。
1、结束条件:如果临时字符串tem的大小与给定字符串str的大小相同,说明已经成功生成了一个与str相同的序列,此时将这个序列添加到结果集res中,并返回。
2、栈非空时的操作:如果栈不为空,那么从栈顶取出一个字符添加到tem中,并递归调用stackSeq函数来继续处理剩余的情况。递归调用返回后,需要“撤销”这次操作,即把之前从栈顶取出的字符重新压回栈中,并从tem中移除这个字符,以便尝试其他可能的序列。
3、插入操作:如果索引index还没有遍历完str中的字符,那么就将str[index]压入栈中,并递增index,然后递归调用stackSeq函数。递归调用返回后,同样需要“撤销”这次操作,即弹出栈顶的字符,并递减index。
void stackSeq(stack<char> &st, string str, int &index, string &tem, vector<string> &res) {//定义结束条件if (tem.size() == str.size()){res.push_back(tem);return;}//只要栈不为空,就出栈if (st.size()>0){tem += st.top();st.pop();stackSeq(st,str,index,tem,res);st.push(tem.back());//撤回出栈操作tem.pop_back();//回溯}//只要有可以插入的元素,就选择插入if (index < str.size()) {st.push(str[index]);index++;stackSeq(st, str, index, tem, res);st.pop();index--;}
}
