剑指 Offer 38：字符串的排列

• 题目
• 解题
• • 方法一：回溯

题目

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

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

示例:

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

解题

方法一：回溯

这是一道全排列问题，涉及去重
和leetcode-47：全排列 II是一样的思路

class Solution {
public:
    vector<string> res;
    string path;
    void backtracing(string s,vector<bool>& used){
        if(path.size()==s.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<s.size();i++){
            if(i>0&&s[i]==s[i-1]&&used[i-1]==false) continue;
            if(used[i]==false){
                used[i]=true;
                path.push_back(s[i]);
                backtracing(s,used);
                path.pop_back();
                used[i]=false;
            }
        }
    }
    vector<string> permutation(string s) {
        sort(s.begin(),s.end());
        vector<bool> used(s.size(),false);
        backtracing(s,used);
        return res;

    }
};