剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

解题思路：

对于这种题目，我们可以首先画出递归树，确定状态变量，确定结束条件，剪枝等

对于此题，我们可以使用used表示该字母是否已经被遍历，那么我们在固定一个字符，遍历下面的字符时，只需要判断used == false即可

AC代码：

class Solution {
public:
    vector<string> res;
    vector<string> permutation(string s) {
        if(s.size() == 0){
            return {};
        }
        string temp = "";
        //sort(s.begin(),s.end());
        vector<bool> used(s.size());
        recur(s,temp,used);
        return res;
    }
    void recur(string s,string& path,vector<bool>& used){
        if(path.size() == s.size()){
            res.push_back(path);
            return;
        }
        for(int i = 0;i < s.size();i++){
            if(!used[i]){
                if(i >= 1&&s[i-1] == s[i]&&!used[i-1])	//判重剪枝
                continue;
                path.push_back(s[i]);	//做出选择
                used[i] = true;		    //设置当前已被遍历
                recur(s,path,used);		//进入下一层递归
                used[i] = false;		//撤销选择，回溯
                path.pop_back();		//撤销选择，回溯
            }
        }
    }
};