剑指 Offer 38. 字符串的排列 / LeetCode 47. 全排列 II（回溯法）

题目：

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

难度：中等

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

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

示例:

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

限制：

• 1 <= s 的长度 <= 8

回溯法：

本题与LeetCode 47. 全排列 II基本相同，详细解析看这篇回溯算法秒杀所有排列/组合/子集问题，这类题型通杀。

代码（剑指 Offer 38. 字符串的排列）：

class Solution {
public:vector<string> res;string track;  // 全局遍历路径vector<bool> used;  // 遍历过程中字符串s每个字符是否在路径中已使用vector<string> permutation(string s) {used = vector<bool>(s.size(), false);sort(s.begin(), s.end());  // 先排序，是为了让重复字符相邻backTrack(s);return res;}void backTrack(string& s) {if(track.size() == s.size()) {  // 一个完整的排列结果加入答案中res.emplace_back(track);return;}for(int i = 0; i < s.size(); i++){if(used[i]) continue;  // 已经在路径中的字符不再参与if(i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;  // 剪枝，固定重复的字符在排列中的相对位置track += s[i];used[i] = true;backTrack(s);  // 进入下一层决策树track.pop_back();  // 回溯used[i] = false;}}
};

代码（LeetCode 47. 全排列 II）：

class Solution {
public:vector<vector<int>> res;vector<int> track;vector<bool> used;vector<vector<int>> permuteUnique(vector<int>& nums) {used.resize(nums.size(), false);sort(nums.begin(), nums.end());backTrack(nums);return res;}void backTrack(vector<int>& nums) {if(track.size() == nums.size()) {res.emplace_back(track);return;}for(int i = 0; i < nums.size(); i++){if(used[i]) continue;if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;track.emplace_back(nums[i]);used[i] = true;backTrack(nums);track.pop_back();used[i] = false;}}
};

时间复杂度O(N * N！)。全部的排列有O(N！)个，每个排列平均需要O(N)的时间。
空间复杂度O(N)。