题解 | #字符串的排列#

class Solution {
public:
    //本题本质上就是数字的排列问题
    //注意本题会有重复字符的情况所以要考虑去重
    vector<string> res;//结果数组
    string path="";//用来暂存每一个叶子的值
    //递归函数的含义为返回string所有的排列
    //used数组是用来标记某个位置上的数组元素是否已经被使用过
    void process(string str,bool used[]){
        //base case
        //当路径path的大小==str的大小时说明所有的元素都被使用过了，此时返回
        if(path.size()==str.size()){
            res.push_back(path);//放入结果数组中
            return ;
        }
        //因为是排列问题所以每一次都要从头开始
        for(int index=0;index<str.size();index++){
            if(!used[index]||(index!=0&&str[index]==str[index-1]&&used[index-1])){//说明这个位置的值已经被用过或者是重复了
                continue;//直接跳过
            }
            else{
                path.push_back(str[index]);
                used[index]=false;
                process(str, used);//递归
                path.pop_back();//回溯
                used[index]=true;//回溯
            }
        }
    }
    vector<string> Permutation(string str) {
        if(str=="")
            return res;
        bool used[str.size()];
        for(int i=0;i<str.size();i++){
            used[i]=true;//true代表没有被使用过
        }
        process(str, used);
        return res;
    }
};