剑指Offer-字符串的排列（中等）

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

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

就全排列

class Solution {
public:
    int len;
    vector<bool> used;//保存状态
    vector<string> ans;//保存输出结果
    vector<char> temp;//保存每个string中的元素
    vector<string> permutation(string s) {
        len=s.length();
        used.resize(len);
        sort(s.begin(),s.end());//先排序，将重复的放在一起
        dfs(s);
        return ans;
    }
    void dfs(string s){
        if(temp.size()==len) {
            string t;
            for(auto i:temp) t+=i; 
            ans.push_back(t);
            return;
        }
        for(int i=0;i<len;i++){
            if(!used[i]){//没有被占用
                if(i>0&&s[i]==s[i-1]&&used[i-1]==false) continue;//减枝
                temp.push_back(s[i]);
                used[i]=true;
                dfs(s);
                used[i]=false;
                temp.pop_back();
            }
        }
    }
};