回溯算法——全排列问题

穿梭的编织者

于 2025-05-18 07:12:44 发布

阅读量231

点赞数 8

分类专栏： # hello算法学习笔记文章标签：算法数据结构

本文链接：https://blog.csdn.net/kouweizhu/article/details/147320314

版权

hello算法学习笔记专栏收录该内容

30 篇文章

订阅专栏

一、介绍

全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找出这个集合中元素的所有可能的排列。下表列举了几个示例数据，包括输入数组和对应的所有排列。

二、无相等元素的情况

输入一个整数数组，数组中不包含重复元素，返回所有可能的排列。

从回溯算法的角度看，我们可以把生成排列的过程想象成一系列选择的结果。假设输入数组为[1,2,3]，如果我们先选择1、再选择3、最后选择2，则获得排列[1,3,2]。回退表示撤销一个选择，之后继续尝试其他选择。

从回溯代码的角度看，候选集合 choices 是输入数组中的所有元素，状态请注意，每个元素只允许被选择一次，因此 state 是直至目前已被选择的元素。 state 中的所有元素都应该是唯一的。

如图所示，我们可以将搜索过程展开成一个递归树，树中的每个节点代表当前状态state 。从根节点开始，经过三轮选择后到达叶节点，每个叶节点都对应一个排列。

1. 重复选择剪枝

为了实现每个元素只被选择一次，我们考虑引入一个布尔型数组 selected，其中是否已被选择，并基于它实现以下剪枝操作。

‧ 在做出选择 choice[i] 后，我们就将 selected[i]表示 choices[i] selected[i] 赋值为 True ，代表它已被选择。

‧ 遍历选择列表 choices 时，跳过所有已被选择过的节点，即剪枝。

如图所示，假设我们第一轮选择1，第二轮选择3，第三轮选择2，则需要在第二轮剪掉元素1的分支，在第三轮剪掉元素1和元素3的分支。

观察上图发现，该剪枝操作将搜索空间大小从𝑂(𝑛𝑛)降低至𝑂(𝑛!)

代码实现：

def backtrack(
    state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
    """回溯算法：全排列 I"""
    # 当状态长度等于元素数量时，记录解
    if len(state) == len(choices):
        res.append(list(state))
        return
    # 遍历所有选择
    for i, choice in enumerate(choices):
        # 剪枝：不允许重复选择元素
        if not selected[i]:
            # 尝试：做出选择，更新状态
            selected[i] = True
            state.append(choice)
            # 进行下一轮选择
            backtrack(state, choices, selected, res)
            # 回退：撤销选择，恢复到之前的状态
            selected[i] = False
            state.pop()


def permutations_i(nums: list[int]) -> list[list[int]]:
    """全排列 I"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res


"""Driver Code"""
if __name__ == "__main__":
    nums = [1, 2, 3]

    res = permutations_i(nums)

    print(f"输入数组 nums = {nums}")
    print(f"所有排列 res = {res}")

三、有相等元素的情况

输入一个整数数组，数组中可能包含重复元素，返回所有不重复的排列。

假设输入数组为[1,1,2]。为了方便区分两个重复元素1，我们将第二个1记为1。如下图所示，上述方法生成的排列有一半都是重复的。

那么如何去除重复的排列呢？最直接地，考虑借助一个哈希表，直接对排列结果进行去重。然而这样做不够优雅，因为生成重复排列的搜索分支是没有必要的，应当被提前识别并剪枝，这样可以进一步提升算法效率。

1. 相等元素剪枝

观察下图，在第一轮中，选择1或选择1是等价的，在这两个选择之下生成的所有排列都是重复的。因此应该把1剪枝掉。同理，在第一轮选择2之后，第二轮选择中的1和1也会产生重复分支，因此也应将第二轮的1剪枝。本质上看，我们的目标是在某一轮选择中，保证多个相等的元素仅被选择一次。

2. 代码实现

def backtrack(
    state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
    """回溯算法：全排列 II"""
    # 当状态长度等于元素数量时，记录解
    if len(state) == len(choices):
        res.append(list(state))
        return
    # 遍历所有选择
    duplicated = set[int]()
    for i, choice in enumerate(choices):
        # 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
        if not selected[i] and choice not in duplicated:
            # 尝试：做出选择，更新状态
            duplicated.add(choice)  # 记录选择过的元素值
            selected[i] = True
            state.append(choice)
            # 进行下一轮选择
            backtrack(state, choices, selected, res)
            # 回退：撤销选择，恢复到之前的状态
            selected[i] = False
            state.pop()


def permutations_ii(nums: list[int]) -> list[list[int]]:
    """全排列 II"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res


"""Driver Code"""
if __name__ == "__main__":
    nums = [1, 2, 2]

    res = permutations_ii(nums)

    print(f"输入数组 nums = {nums}")
    print(f"所有排列 res = {res}")

假设元素两两之间互不相同，则𝑛个元素共有𝑛!种排列（阶乘）；在记录结果时，需要复制长度为𝑛的列表，使用𝑂(𝑛)时间。因此时间复杂度为𝑂(𝑛!𝑛)。

最大递归深度为𝑛，使用𝑂(𝑛)栈帧空间。selected使用𝑂(𝑛)空间。同一时刻最多共有𝑛个duplicated，使用𝑂()空间。因此空间复杂度为𝑂()。