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

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

示例

• 输入：s = "abc"

• 输出：["abc","acb","bac","bca","cab","cba"]

限制

• 1 <= s 的长度 <= 8

方法：回溯法

dfs方法：

• 如果是最后一位，说明是最后一种排列，转化为字符串加入到结果中；

• 创建一个 HashSet 集合用于排除重复的值；

• 如果 固定的值 存在 set 集合中，代表其是重复字符，不作处理，直接跳过；

• 否则将 固定的值 加入到 set 集合中，之后用做去重处理；

• 将 固定的值 和 当前值 交换；

• 开始递归遍历 下一个值；

• 递归完毕后，还原之前的值。

permutation方法：

• 把字符串转化为字符数组；

• 进行递归遍历；

• 返回结果字符串数组。

代码如下：

复杂度分析

• 时间复杂度：O(N!N)，N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 N×(N−1)×(N−2)…×2×1 ，即复杂度为 O(N!) ；字符串拼接操作 join() 使用 O(N) ；因此总体时间复杂度为 O(N!N) 。

• 空间复杂度 ：O(N的2次方) ，全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N) ；递归中辅助 Set 累计存储的字符数量最多为 N+(N−1)+...+2+1=(N+1)N/2 ，即占用 O(N的2次方) 的额外空间。

END

只要功夫深，铁杵磨成针，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。