[Leetcode] [Tutorial] 回溯

---

46. 全排列

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

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

Solution

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(path):if len(path) == len(nums):res.append(path[:])returnfor num in nums:if num not in path:path.append(num)backtrack(path)path.pop()res = []backtrack([])return res

在backtrack函数中，我们通过一个for循环来遍历nums中的所有元素，并尝试将其添加到path的末尾。每当我们递归调用backtrack函数后，我们就会移除path的最后一个元素，并在下一次for循环迭代中尝试添加下一个元素。

78. 子集

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

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

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

Solution

class Solution:def subsets(self, 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

我们可以还使用位掩码（bitmask）的方法。

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:n = len(nums)output = []for i in range(2**n):# generate bitmask, from 0..00 to 1..11bitmask = bin(i)[2:].zfill(n)# append subset corresponding to that bitmaskoutput.append([nums[j] for j in range(n) if bitmask[j] == '1'])return output

bin(i)是 Python 的内置函数，用于将整数 i 转换成二进制字符串。例如，bin(3) 将返回 ‘0b11’。‘0b’ 是表示这是一个二进制数。

.zfill(n)是 Python 字符串的一个方法，用于在字符串前面填充 0，直到字符串的长度为 n。例如，‘11’.zfill(3) 将返回 ‘011’。

17. 电话号码的字母组合

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

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

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Solution

39. 组合总和

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

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

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

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

Solution

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def backtrack(target, path, start):if target == 0:res.append(path[:])returnfor i in range(start, len(candidates)):if candidates[i] > target:continuepath.append(candidates[i])backtrack(target - candidates[i], path, i)path.pop()res = []backtrack(target, [], 0)return res

22. 括号生成

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

示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

Solution

class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(s, left, right):if len(s) == n * 2:res.append(''.join(s))returnif left < n:s.append('(')left += 1backtrack(s, left, right)s.pop()left -= 1if left > right:s.append(')')right += 1backtrack(s, left, right)s.pop()right -= 1res = []backtrack([], 0, 0)return res

s是一个字符列表，当你要将最终结果添加到res时，你需要用 ‘’.join(s) 把s转换为字符串。

实际上，left和right的值都可以自动“回溯”到他们在函数调用开始时的状态。

class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(s, left, right):if len(s) == n * 2:res.append(s)returnif left < n:backtrack(s + '(', left + 1, right)if right < left:backtrack(s + ')', left, right + 1)res = []backtrack('', 0, 0)return res