字符串排列(系列)

全排列

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

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

 

示例:

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

回溯

其实就是穷举法

从左往右依次填入字符，为了避免在同一位置填入相同元素需要设置一个标记数组来记录元素访问情况

class Solution:
    def permutation(self, s: str) -> List[str]:
        def backtrack(s, i, n, res):
            if i == n:
                result.append(res)
                return

            for j in range(n):
                if visited[j] or (j > 0 and not visited[j-1] and s[j-1]==s[j]):
                    continue
                visited[j] = True
                res += s[j]
                backtrack(list(s), i+1, n, res)
                visited[j] = False
                res = res[:-1]
        result = []
        n = len(s)
        visited = [False]*n
        s = list(s)
        s.sort()
        backtrack(s, 0, n, "")
        return result

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

---

class Solution {
    vector<int> vis;
public:
    void backtrack(vector<vector<int>>& ans, vector<int>& perm, int index, vector<int>& nums){
            if (index == nums.size()){
                ans.emplace_back(perm);
                return;
            }
            for (int i = 0; i < nums.size(); i++){
                if (vis[i] || (i > 0 && nums[i-1] == nums[i] && !vis[i-1])) continue;
                perm.emplace_back(nums[i]);
                vis[i] = 1;
                backtrack(ans, perm, index+1, nums);
                vis[i] = 0;
                perm.pop_back();
            }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vis.resize(nums.size());
        vector<vector<int>> ans;
        vector<int> perm;
        sort(nums.begin(), nums.end());
        backtrack(ans, perm, 0, nums);
        return ans;
    }
};