力扣hot100题解（python版55-59题）

55、全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

思路解答：

  1. 递归生成排列： 通过递归函数 backtrack，在每一步尝试将当前位置的元素与后续位置的元素交换，然后递归处理下一个位置。
  2. 交换元素： 在每一步尝试中，通过交换元素的位置来生成不同的排列，这样可以确保每个元素都出现在每个位置上。
  3. 回溯： 在递归调用完成后，需要恢复元素的原始顺序，以便进行下一次尝试。这样可以确保不会遗漏任何可能的排列。
  4. 终止条件： 当处理到列表的最后一个位置时（first == n-1），即已经生成了一个完整的排列，将该排列加入结果列表中。
def permute(nums: list[int]) -> list[list[int]]:
    def backtrack(first):
        if first == n-1:
            res.append(list(nums))
            return
        for i in range(first, n):
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]

    n = len(nums)
    res = []
    backtrack(0)
    return res

56、子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

思路解答：

  1. 回溯生成子集： 使用回溯算法生成所有可能的子集。回溯算法的特点是尝试所有可能的选择，并在每一步都进行回溯，以便尝试其他选择。
  2. 递归生成子集： 定义了一个内部函数 backtrack(start, path)，其中 start 表示当前处理的起始位置，path 表示当前的子集路径。
  3. 添加子集： 在每次递归调用开始时，将当前的 path 子集加入到结果列表 res 中，这样可以确保不漏掉任何子集。
  4. 遍历元素： 遍历从 start 到 len(nums) 的位置，将当前元素加入到 path 中，然后递归调用 backtrack(i + 1, path) 处理下一个位置。
  5. 回溯操作： 在递归调用完成后，需要将最后一个加入的元素从 path 中移除，以便尝试其他选择。
  6. 初始化及返回： 在函数主体中，初始化结果列表 res 为空列表，然后调用 backtrack(0, []) 开始生成子集。最后返回结果列表 res，其中包含了给定列表 nums 的所有子集。
def subsets(nums: list[int]) -> list[list[int]]:
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    res = []
    backtrack(0, [])
    return res

57、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

思路解答：

  1. 递归实现：通过递归实现回溯算法，在每一步都遍历当前数字对应的所有字母，并递归调用下一层。
  2. 遍历元素： 遍历当前数字对应的字符位置，将当前元素加入到 path 中，然后递归调用 backtrack(index + 1, path) 处理下一个位置。
  3. 回溯操作： 在递归调用完成后，需要将最后一个加入的元素从 path 中移除，以便尝试其他选择。
  4. 终止条件：当遍历完所有字符时，将当前的字符组合加入结果集中。
def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []

    phone = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

    def backtrack(index, path):
        if index == len(digits):
            res.append(''.join(path))
            return

        for char in phone[digits[index]]:
            path.append(char)
            backtrack(index + 1, path)
            path.pop()

    res = []
    backtrack(0, [])
    return res

58、组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路解答：

  1. 排序候选列表：首先对候选列表进行排序，这样可以在回溯的过程中更方便地控制搜索顺序。

  2. 回溯函数：编写一个回溯函数 backtrack(start, path, target)，其中：

    • start：表示当前可以选择的候选元素的起始位置，避免重复组合；
    • path：记录当前的组合；
    • target：表示目标数值。

  3. 回溯过程：

    • 如果 target == 0，将当前的组合加入结果集；
    • 如果 target < 0，直接返回，不再继续向下搜索；
    • 遍历候选列表中的元素：
      • 将当前元素加入组合 path 中；
      • 递归调用 backtrack，更新 target 为 target - candidates[i]，起始位置为 i；
      • 在递归调用返回后，将当前元素从组合 path 中移除，继续下一个元素的搜索。
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:

    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, target - candidates[i])
            path.pop()

    res = []
    candidates.sort()
    backtrack(0, [], target)
    return res

59、括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

思路解答：

  1. 递归函数设计：

    • 设计一个递归函数，函数参数包括左括号数量 left、右括号数量 right、当前组合 path。

  2. 终止条件：

    • 当当前组合长度达到 2 * n 时，将当前组合加入结果集。

  3. 递归过程：

    • 在递归过程中，考虑两种情况：
      • 可以添加左括号的条件是 left < n。
      • 可以添加右括号的条件是 right < left。

  4. 回溯过程：

    • 在回溯过程中，分别尝试添加左括号和右括号，并递归调用下一层。
def generateParenthesis(n: int) -> list[str]:

    def backtrack(left, right, path):
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if left < n:
            path.append('(')
            backtrack(left + 1, right, path)
            path.pop()
        if right < left:
            path.append(')')
            backtrack(left, right + 1, path)
            path.pop()

    res = []
    backtrack(0, 0, [])
    return res