剑指Offer - 面试题38. 字符串的排列（全排列，排序，回溯+剪枝）
1. 题目
作者：Michael阿明
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
相关题目：
LeetCode 46. 全排列（回溯）
LeetCode 47. 全排列 II（回溯+搜索剪枝）
class Solution {
int n;
vector ans;
string str;
public:
vector permutation(string s) {
sort(s.begin(), s.end());//先排序，后面好剪枝，跳过重复的
n = s.size();
vector visited(n,false);//访问过某字符了
bt(s,0,visited);
return ans;
}
void bt(string& s, int count, vector& visited)
{
if(count == n)
{
ans.push_back(str);
return;
}
for(int i = 0; i < n; ++i)
{
if(!visited[i])
{
if(i != 0 && s[i-1] == s[i] && visited[i-1])
//if(i != 0 && s[i-1] == s[i] && !visited[i-1])
continue;//前一个字符等于当前，跳过
//有无!差别是剪枝顺序差别
//推荐第二种写法，剪枝更彻底
visited[i] = true;
str.push_back(s[i]);
bt(s,count+1,visited);
str.pop_back();
visited[i] = false;
}
}
}
};
参考解题
作者：Michael阿明
相关文章
Xena
2020-07-03
Tertia
2020-10-26
Aggie
2020-09-20
Kathy
2020-03-08
Serafina
2020-03-27
Veronica
2020-04-14
Letitia
2020-11-27
Catherine
2023-07-21
Rabia
2023-07-21
Linnea
2023-07-21
Natalia
2023-07-21
Ula
2023-07-21
Jennifer
2023-07-21
Jayne
2023-07-21
Maleah
2023-07-21
Bella
2023-07-21
Coral
2023-07-21
Talia
2023-07-21