> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/jian-zhi-offer3800-zhong-deng-zi-fu-chuan-de-pai-lie-quan-pai-lie.md).
# 字符串的排列（全排列）
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#中等) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#剑指offer) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#深度优先搜索) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#经典)
**问题简述**
```
输入一个字符串，打印出该字符串中字符的所有排列。
```
详细描述
```
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
**思路1：DFS树状遍历+剪枝**
* 深度优先求全排列的过程实际上相当于是一个**多叉树的先序遍历过程**；
* 假设共有 `n` 种状态都不重复，则：
* 第一层有 `n` 种选择；
* 第二层有 `n - 1` 种选择；
* ...
* 共有 `n!` 种可能；
**本题的难点是如何过滤重复的状态**
* **写法1）** 遍历所有状态，直接用 `set` 保存结果（不剪枝）：
* **写法2）** 跳过重复字符（需排序）：
* 其中用于剪枝的代码不太好理解，其解析详见：[「代码随想录」剑指 Offer 38. 字符串的排列](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/dai-ma-sui-xiang-lu-jian-zhi-offer-38-zi-gwt6/)
```python
if not visited[i - 1] and i > 0 and s[i] == s[i - 1]:
continue
```
* **写法3）** 在每一层用一个 `set` 保存已经用过的字符（不排序）：
* **写法2）** 原地交换
> [剑指 Offer 38. 字符串的排列（回溯法，清晰图解）](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/)
* 这个写法有点像“下一个排列”，只是没有使用字典序；
**思路2：下一个排列**
> [字符串的排列](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-hhvs/)
* 先排序得到最小的字典序结果；
* 循环直到不存在下一个更大的排列；
Python
```python
class Solution:
def permutation(self, s: str) -> List[str]:
def nextPermutation(nums: List[str]) -> bool:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False
else:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return True
buf = sorted(s)
ret = [''.join(buf)]
while nextPermutation(buf):
ret.append(''.join(buf))
return ret
```