题目描述

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

样例

示例1:

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:

 输入：S = "ab"
 输出：["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

算法1

(dfs)

C++ 代码

class Solution {
public:
    vector<string> res;
    bool st[100010];
    void dfs(int u,int len,string now,string S)
    {
        if(u==len)
        {
            res.push_back(now);
            return;
        }
        for(int i = 0 ; i < len; i++)
        {
            if(!st[i])
            {
                st[i] = true;
                now += S[i];
                dfs(u+1,len,now,S);
                now.erase(now.size()-1);
                st[i] = false;
            }
        }
    }
    vector<string> permutation(string S) {
        dfs(0,S.size(),"",S);
        return res;
    }
};