行业知识

【力扣hot100】刷题笔记Day17

2026-10-29 20:23:34 来源：互联网转载

前言

今天��然不用开组会！天大的好消息，安心刷题了

46. 全排列 - 力扣（LeetCode）

回溯（排列）

class Solution:    def permute(self, nums: List[int]) -> List[List[int]]:        # 回溯        def backtrack():            if len(path) == len(nums):                res.append(path[:])  # 如果path长度达到要求，收集结果，注意python要拷贝res                return             for i in range(len(nums)):                if used[i] == 0:  # 遍历所有没用过的                    used[i] = 1                    path.append(nums[i])                    backtrack()                    path.pop()  # 撤销                    used[i] = 0  # 撤销        # 可变对象在函数中可以直接改不需要作为参数，也不需要写self，只有赋值需要        # 比如：递归里self.res= max(self.res，l+r)需要用self或递归里nonlocal res声明        n = len(nums)        used = [0] * n        path = []        res = []        backtrack()        return res

回溯（交换填充）

class Solution:    def permute(self, nums: List[int]) -> List[List[int]]:        def backtrack(first = 0):            # 所有数都填完了            if first == n:                  res.append(nums[:])            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()        return res

78. 子集 - 力扣（LeetCode）

回溯（组合）

class Solution:    def subsets(self, nums: List[int]) -> List[List[int]]:        def backtrack(start=0):            res.append(path[:])  # 每到一个节点就传一次答案            # if start == n: return  # 下面的for循环隐含这个终止条件            for i in range(start, n):                path.append(nums[i])                backtrack(i+1)  # 注意这里传入的是i+1                path.pop()        n = len(nums)        res = []        path = []        backtrack(0)        return res

17. 电话号码的字母组合 - 力扣（LeetCode）

回溯（不同集合的组合）

class Solution:    def letterCombinations(self, digits: str) -> List[str]:        def backtrack(index = 0):            if index == len(digits):                res.append("".join(path))  # 不用传复制因为已经新建字符串了                return            s = mp[int(digits[index])]  # 取出对应数字的字符串            for c in s:                path.append(c)                backtrack(index+1)                path.pop()        if len(digits) == 0:            return []        mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']  # 下标号码映射字符串        path = []        res = []        backtrack()        return res

39. 组合总和 - 力扣（LeetCode）

回溯（排序剪枝）

class Solution:    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:        path = []        res = []        n = len(candidates)        def backtrack(start, target):            if target

22. 括号生成 - 力扣（LeetCode）

回溯（组合）

这个题解结合官解就能看懂了，主要在于括号合法性判断上

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        if n  n or right > left: return            if len(path) == 2 * n:  # 因为括号都是成对出现的                res.append(path)                return            backtrack(path + '(', left + 1, right)  # 生成一个加一个            backtrack(path + ')', left, right + 1)        backtrack('', 0, 0)        return res