代码随想录算法训练营第二十二天 | 回溯算法 Part04

585 字

3 分钟

代码随想录算法训练营第二十二天 | 回溯算法 Part04

2025-07-05

算法

全排列问题

/

算法

/

LeetCode

/

Python

全排列问题（Permutation）#

全排列是回溯算法中的高级应用，目标是在一个集合中找出所有可能的排列方式。
它强调顺序性，并且需要追踪每个元素是否已经使用。

🔸 考点梳理#

✅ 元素是否已使用（通常需要布尔数组或 set 标记）
✅ 去重：对输入排序 + 跳过重复分支
✅ 特殊问题（如 N 皇后）：在排列基础上加入位置合法性判断

491. 递增子序列#

LeetCode 491. 递增子序列

1
class Solution:
2
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        self.backtrack(nums, 0)
6
        return self.res
7

8
    def backtrack(self, nums, start):
9
        if len(self.path) >= 2:
10
            self.res.append(self.path[:])
11
        # 记录本层使用过的数字，防止同一层重复使用相同元素
12
        used = set()
13
        for i in range(start, len(nums)):
14
            if self.path and self.path[-1] > nums[i]:
15
                continue  # 递增限制
16
            if nums[i] in used:
17
                continue  # 同层去重
18
            used.add(nums[i])
19
            self.path.append(nums[i])
20
            self.backtrack(nums, i + 1)
21
            self.path.pop()

46. 全排列#

LeetCode 46. 全排列

1
class Solution:
2
    def permute(self, nums: List[int]) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        self.used = []
6
        self.backtrack(nums)
7
        return self.res
8

9
    def backtrack(self, nums):
10
        if len(self.path) == len(nums):
11
            self.res.append(self.path[:])
12
            return
13
        for i in range(len(nums)):
14
            if nums[i] in self.used:
15
                continue
16
            self.path.append(nums[i])
17
            self.used.append(nums[i])
18
            self.backtrack(nums)
19
            self.path.pop()
20
            self.used.pop()

47. 全排列 II（含重复元素）#

LeetCode 47. 全排列 II

1
class Solution:
2
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        self.used = [False] * len(nums)
6
        nums.sort()  # 排序是剪枝的前提
7
        self.backtrack(nums)
8
        return self.res
9

10
    def backtrack(self, nums):
11
        if len(self.path) == len(nums):
12
            self.res.append(self.path[:])
13
            return
14
        for i in range(len(nums)):
15
            if self.used[i]:
16
                continue
17
            # 剪枝：前一个值和当前值相等，且前一个值还未使用，则跳过
18
            if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
19
                continue
20
            self.path.append(nums[i])
21
            self.used[i] = True
22
            self.backtrack(nums)
23
            self.path.pop()
24
            self.used[i] = False

51. N 皇后#

LeetCode 51. N 皇后

1
class Solution:
2
    def solveNQueens(self, n: int) -> List[List[str]]:
3
        self.res = []
4
        board = ["." * n for _ in range(n)]  # 初始化棋盘
5
        self.backtrack(board, 0)
6
        return self.res
7

8
    def backtrack(self, board: List[str], row: int) -> None:
9
        if row == len(board):
10
            self.res.append(board[:])  # 注意需复制当前棋盘
11
            return
12
        n = len(board)
13
        for col in range(n):
14
            if not self.isValid(board, row, col):
15
                continue
16
            # 放置皇后
17
            board[row] = board[row][:col] + 'Q' + board[row][col + 1:]
18
            self.backtrack(board, row + 1)
19
            # 撤销选择
20
            board[row] = board[row][:col] + '.' + board[row][col + 1:]
21

22
    def isValid(self, board: List[str], row: int, col: int) -> bool:
23
        n = len(board)
24
        # 检查列是否有皇后
25
        for i in range(row):
26
            if board[i][col] == 'Q':
27
                return False
28
        # 检查右上对角线
29
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
30
            if board[i][j] == 'Q':
31
                return False
32
        # 检查左上对角线
33
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
34
            if board[i][j] == 'Q':
35
                return False
36
        return True