题解 | #字符串的排列#

//定义全局变量，也可以放在函数参数中
vector<string> res;
string path;
//递归回溯函数
void backtrack(string str,vector<bool> used){
    //终止条件，当路径的个数与str的个数相同
    //也可以用used判断，当used权威true时，也是正确结果
    if(path.size()==str.size()){
        res.push_back(path);
        return ;
    }
    //因为是排列问题，每次循环都是从0开始的，每次需要把上一次的去除
    //也就是用used进行标注的好处
    for(int i=0;i<str.size();i++){
        //这个条件很重要，剪枝操作，去除重复元素
        //在当前值遇上一个值相同并且上一个值已经选择的情况下，可以跳出此次循环
        if(used[i]||(i>0&&str[i]==str[i-1]&&used[i-1]))
            continue;
        //下面就是正常的单层逻辑，先添加，并赋true
        path.push_back(str[i]);
        used[i]=true;
        //递归调用
        backtrack(str, used);
        //回溯操作，赋false，并取出元素
        used[i]=false;
        path.pop_back();
    }
}
vector<string> Permutation(string str) {
    //首先判断是否为空，空直接返回
    if(str.empty())
        return res;
    //由于有重复元素，需要先进行排序，将相同的元素放到一起
    sort(str.begin(),str.end());
    //used数组初始化为false
    vector<bool> used(str.size(),false);
    //进行递归回溯
    backtrack(str, used);
    //返回结果
    return res;
}