剑指 Offer 38. 字符串的排列 力扣（中等） 排列回溯，不会

题目描述：

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

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

示例:

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

 

限制：

1 <= s 的长度 <= 8

题源：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

题解：

用回溯全排列，回溯写全排列忘记了，然后主要是这题数据较小，所以可以用回溯写

class Solution {
    vector<string> res,ans;
public:
    void dfs(string s,int k)
    {
        if(k==s.size()-1)
        {
            res.push_back(s);
            return;
        }
        set<char> flag;
        for(int i=k;i<s.size();i++)
        {
            if (flag.find(s[i])!=flag.end()) continue;   //如果在k这个位置出现过同样的字母，就不继续了。
            flag.insert(s[i]);
            swap(s[i],s[k]);
            dfs(s,k+1);
            swap(s[i],s[k]);
        }
    }
    vector<string> permutation(string s) {
     dfs(s,0);
     ans.assign(res.begin(),res.end());
     return ans;
    }
};

示例:

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