剑指 Offer 38. 字符串的排列

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

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

示例:

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

class Solution {
public:
vector<string> res;
 void backtrack(string s,string& path,vector<bool>& used)//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;
                backtrack(s,path,used);
                used[i]=false;
                path.pop_back();
            }   
        }
    }

vector<string> permutation(string s) {
        if(s.size()==0)
            return{};
        string temp="";
        sort(s.begin(),s.end());
        vector<bool>used(s.size());
        backtrack(s,temp,used);
        return res;
    }
};