leetcode 链接：剑指 Offer 38. 字符串的排列

题目

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


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

示例：

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

解答 & 代码

递归回溯，但要注意去重

class Solution {
private:
    void findPermutations(string s, int idx, vector<string>& resultList)
    {
        int size = s.size();
        // 递归结束条件，如果当前遍历到字符串的最后一个位置，则将当前的字符串存入结果数组
        if(idx == size - 1)
        {
            resultList.push_back(s);
            return;
        }            

        // map 用于去重，存储在当前位置已经出现过的字符，如果再次出现这个字符，则跳过
        unordered_set<int> map;
        for(int i = idx; i < size; ++i)
        {
            // 如果已经在当前位置放过字符 s[i]，则跳过
            if(map.find(s[i]) != map.end())
                continue;
            // 否则，将s[i]插入哈希表
            map.insert(s[i]);

            swap(s[idx], s[i]);        // 交换 s[i] 到当前位置
            findPermutations(s, idx + 1, resultList);
            swap(s[idx], s[i]);     // 回溯
        }
    }
public:
    vector<string> permutation(string s) {
        vector<string> resultList;
        findPermutations(s, 0, resultList);
        return resultList;
    }
};

执行结果：

执行结果：通过

执行用时：104 ms, 在所有 C++ 提交中击败了 27.84% 的用户
内存消耗：33.7 MB, 在所有 C++ 提交中击败了 15.15% 的用户