M02748: 全排列

dfs, backtracking, http://cs101.openjudge.cn/pctbook/M02748/

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

输出

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得 s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。

样例输入

abc

样例输出

abc
acb
bac
bca
cab
cba

递归构造

from typing import List

class Solution:
    def permute(self, s: str) -> List[str]:
        ans = []

        def back(remaining: str, path: str):
            if not remaining:
                ans.append(path)
                return
            for i in range(len(remaining)):
                back(remaining[:i] + remaining[i+1:], path + remaining[i])

        back(s, "")
        return ans


# 测试
s = input().strip()
solution = Solution()
for p in solution.permute(s):
    print(p)

def permute(s: str):
    ans = []

    def back(remaining: str, path: str):
        if not remaining:
            ans.append(path)
            return
        for i in range(len(remaining)):
            back(remaining[:i] + remaining[i+1:], path + remaining[i])

    back(s, "")
    return ans


# 测试
s = input().strip()
for p in permute(s):
    print(p)

这不是真正意义上的“显示回溯”。每次递归调用，都创建了新的字符串 remaining[:i] + remaining[i+1:] 和 path + remaining[i]，相当于把状态拷贝了一份，然后递归下去。

回溯法的核心是在原地修改状态，再递归，递归结束后再恢复状态，例如：

• 用一个数组 used 来记录已使用元素；
• 在递归前标记为已用，递归结束后再取消标记，这就是经典的“显示回溯”。

真正显示回溯的版本（不产生新的子串/新字符串，而是在原数组上操作 + 回溯恢复），可以这样写：

def permute(s: str):
    ans = []
    s = list(s)  # 转为列表，方便原地交换

    def back(start):
        if start == len(s):
            ans.append(''.join(s))
            return
        for i in range(start, len(s)):
            s[start], s[i] = s[i], s[start]  # 交换
            back(start + 1)
            s[start], s[i] = s[i], s[start]  # 回溯恢复

    back(0)
    return ans

# 测试
s = input().strip()
for p in permute(s):
    print(p)

✅ 特点

• 原地交换，不产生额外子串；
• 显示回溯（swap + swap back）；
• 时间复杂度和递归构造一样，但空间利用更高效。

这是一个经典的 全排列（permutation）生成问题，可以用 回溯法（backtracking） 或 Python 内置库解决。下面我给出三种解法并解释思路。

---

解法一：回溯法（推荐理解用）

def backtrack(path, used, s):
    if len(path) == len(s):
        print(''.join(path))
        return
    for i in range(len(s)):
        if not used[i]:
            used[i] = True
            path.append(s[i])
            backtrack(path, used, s)
            path.pop()
            used[i] = False

s = input().strip()
used = [False] * len(s)
backtrack([], used, s)

思路

1. path：当前排列的部分结果；
2. used[i]：记录字符是否已被使用；
3. 当 path 的长度与原串相同时，输出该排列；
4. 因为输入是按字典序给的（如 "abc"），递归会自然按照字典序输出。

---

解法二：内置库 itertools.permutations（最简洁）

import itertools

s = input().strip()
for p in itertools.permutations(s):
    print(''.join(p))

思路：itertools.permutations(s)会返回按字典序排列的所有元组，如[('a','b','c'), ('a','c','b'), ...]，用 ''.join()` 拼回字符串即可。

---

解法三：递归构造（不显式使用used数组）

def permute(s):
    if len(s) == 1:
        return [s]
    res = []
    for i, ch in enumerate(s):
        for p in permute(s[:i] + s[i+1:]):
            res.append(ch + p)
    return res

for p in permute(input().strip()):
    print(p)

思路：递归时取出一个字符 ch，对剩余部分递归求全排列，再把 ch 拼接在前面。

def dfs(s, path, used, res):
    if len(path) == len(s):
        res.append(''.join(path))
        return
    for i in range(len(s)):
        if not used[i]:
            used[i] = True
            path.append(s[i])
            dfs(s, path, used, res)
            path.pop()
            used[i] = False

def print_permutations(s):
    res = []
    dfs(s, [], [False]*len(s), res)
    for perm in sorted(res):
        print(perm)

# Test the function
print_permutations(input())

from itertools import permutations

def print_permutations(s):
    # Generate all permutations
    perms = permutations(s)

    # Sort the permutations and print each one
    for perm in sorted(perms):
        print(''.join(perm))

print_permutations(input())