题解 | #字符串的排列#

class Solution {
public:

    void subPermutation(string &str,int pos,vector<string> &temp){
        int size=str.size();
        if(pos==size-1)
            temp.push_back(str);
        for(int i=pos;i<size;i++)
        {
            if(i==pos)
                subPermutation(str, pos+1,temp);
            if(str[i]!=str[pos])
            {
                swap(str[pos], str[i]);
                subPermutation(str, pos+1,temp);
                swap(str[pos], str[i]);
            }

        }
    }
    vector<string> Permutation(string str) {
        vector<string> dp;
        if(str.size()==0)
            return dp;
        subPermutation(str,0,dp);
        return dp;
    }
};

都说使用动态规划，但是我还是感觉称之为回溯比较合适，典型的模板题