题解 | #全排列#

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

/**
 *
 * @param preString 前缀字符
 * @param remainStr 除去前缀字符后剩余的字符
 * @return
 */
void fullArrangement(string preStr, string remainStr) {
    if (remainStr.size() == 1) {
        /*
         * 当余下字符串只有一个字符时，表示前缀字符已经确定下来了
         * 因此，我们直接preString 和 remainString 拼接后输出即可
         */
        cout << preStr + remainStr << endl;
        return;
    } else {
        string nextPreStr = "";
        string nextRemainStr = "";
        for (int i = 0; i < remainStr.size(); ++i) {
            nextPreStr = preStr + remainStr[i];
            /*
             * string.erase(i, 1):
             * 剔除string中，从索引i开始的一个字符（即，剔除索引为i的字符）
             *
             * 注意：此处要先将remainStr赋值给nextRemainStr，然后再删除nextRemainStr的第i个索引的字符
             *
             * 因为，递归结束后会进行回溯，所以不能直接执行remainStr.erase(i, 1);
             * 如果直接删除后，会造成同一层fullArrangement函数调用，中的两次for循环的remainStr不同。
             */
            nextRemainStr = remainStr;
            nextRemainStr.erase(i, 1);
            /*
             * 递归调用
             */
            fullArrangement(nextPreStr, nextRemainStr);
        }
    }
}

/**
 * 全排列--北京大学
 * @return
 */
int main() {
    string sequence;
    while (cin >> sequence) {
        fullArrangement("", sequence);
    }

    return 0;
}