全排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解法

    //解法：回溯法
    // 时间O（n*n!） 空间O（1）
    //从pos..n的排列
    void dfs(string & str, int pos, set<string> & ans) {
        if (pos == str.size() - 1) {
            ans.insert(str);
            return;
        }
        for (int i = pos; i < str.size(); i++) { //在pos位置，可以尝试所有未被排列的数字.
            swap(str[pos], str[i]); 
            dfs(str, pos + 1, ans);
            swap(str[pos], str[i]);
        }
    }
    vector<string> Permutation(string str) {
        if (str.empty()) return {};
        set<string> ans;
        dfs(str, 0, ans);
        vector<string> ansVec(ans.begin(), ans.end());
        sort(ansVec.begin(), ansVec.end());
        return ansVec;
    }