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] <= 10nums中的所有整数 互不相同
思路解答：
- 递归生成排列： 通过递归函数
backtrack，在每一步尝试将当前位置的元素与后续位置的元素交换，然后递归处理下一个位置。 - 交换元素： 在每一步尝试中，通过交换元素的位置来生成不同的排列，这样可以确保每个元素都出现在每个位置上。
- 回溯： 在递归调用完成后，需要恢复元素的原始顺序，以便进行下一次尝试。这样可以确保不会遗漏任何可能的排列。
- 终止条件： 当处理到列表的最后一个位置时（
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] <= 10nums中的所有元素 互不相同
思路解答：
- 回溯生成子集： 使用回溯算法生成所有可能的子集。回溯算法的特点是尝试所有可能的选择，并在每一步都进行回溯，以便尝试其他选择。
- 递归生成子集： 定义了一个内部函数
backtrack(start, path)，其中start表示当前处理的起始位置，path表示当前的子集路径。 - 添加子集： 在每次递归调用开始时，将当前的
path子集加入到结果列表res中，这样可以确保不漏掉任何子集。 - 遍历元素： 遍历从
start到len(nums)的位置，将当前元素加入到path中，然后递归调用backtrack(i + 1, path)处理下一个位置。 - 回溯操作： 在递归调用完成后，需要将最后一个加入的元素从
path中移除，以便尝试其他选择。 - 初始化及返回： 在函数主体中，初始化结果列表
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 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路解答：
- 递归实现：通过递归实现回溯算法，在每一步都遍历当前数字对应的所有字母，并递归调用下一层。
- 遍历元素： 遍历当前数字对应的字符位置，将当前元素加入到
path中，然后递归调用backtrack(index + 1, path)处理下一个位置。 - 回溯操作： 在递归调用完成后，需要将最后一个加入的元素从
path中移除，以便尝试其他选择。 - 终止条件：当遍历完所有字符时，将当前的字符组合加入结果集中。
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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
思路解答：
-
排序候选列表：首先对候选列表进行排序，这样可以在回溯的过程中更方便地控制搜索顺序。
-
回溯函数：编写一个回溯函数
backtrack(start, path, target)，其中：start：表示当前可以选择的候选元素的起始位置，避免重复组合；path：记录当前的组合；target：表示目标数值。
-
回溯过程：
- 如果
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
思路解答：
-
递归函数设计：
- 设计一个递归函数，函数参数包括左括号数量
left、右括号数量right、当前组合path。
- 设计一个递归函数，函数参数包括左括号数量
-
终止条件：
- 当当前组合长度达到
2 * n时，将当前组合加入结果集。
- 当当前组合长度达到
-
递归过程：
- 在递归过程中，考虑两种情况：
- 可以添加左括号的条件是
left < n。 - 可以添加右括号的条件是
right < left。
- 可以添加左括号的条件是
- 在递归过程中，考虑两种情况：
-
回溯过程：
- 在回溯过程中，分别尝试添加左括号和右括号，并递归调用下一层。
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
