建游戏网站,体育西网站开发定制,青岛网页建站模板,图书网站怎么做目录 前置知识进入正题小试牛刀实战演练总结 前置知识 【算法】回溯算法专题① ——子集型回溯 python 进入正题 组合https://leetcode.cn/problems/combinations/submissions/596357179/ 给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以… 目录 前置知识进入正题小试牛刀实战演练总结 前置知识 【算法】回溯算法专题① ——子集型回溯 python 进入正题 组合https://leetcode.cn/problems/combinations/submissions/596357179/ 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2 输出 [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
示例 2
输入n 1, k 1 输出[[1]]
提示 1 n 20 1 k n
思路 回溯思路选或不选 / 枚举选哪个 剪枝选不满k个就停止递归 code1
class Solution:def combine(self, n: int, k: int) - List[List[int]]:ans []path []def dfs(i):# 剪枝if n - i 1 len(path) k: returnif len(path) k:ans.append(path.copy())return# 不选dfs(i 1)# 选path.append(i)dfs(i 1)path.pop()dfs(1)return anscode2
class Solution:def combine(self, n: int, k: int) - List[List[int]]:ans []path []def dfs(i):# 剪枝if n - i 1 len(path) k:returnif len(path) k:ans.append(path.copy())return# 枚举选哪个 for j in range(i, n 1):path.append(j)dfs(j 1)path.pop()dfs(1)return ans小试牛刀 组合总和Ⅲ https://leetcode.cn/problems/combination-sum-iii/description/
找出所有相加之和为 n 的 k 个数的组合且满足下列条件 1.只使用数字1到9 2.每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7 输出: [[1,2,4]] 解释: 1 2 4 7 没有其他符合的组合了。
示例 2:
输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 2 6 9 1 3 5 9 2 3 4 9 没有其他符合的组合了。
示例 3:
输入: k 4, n 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。
提示: 2 k 9 1 n 60
思路 与上题一样的思路 回溯 剪枝 题解1
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:ans []path []def dfs(i):# 剪枝if len(path) 10 - i k:returnif sum(path) n:returnif len(path) k and sum(path) n:ans.append(path.copy())return# 选path.append(i)dfs(i 1)path.pop()# 不选dfs(i 1)dfs(1)return ans题解2
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:ans []path []def dfs(i):# 剪枝if len(path) 10 - i k:returnif sum(path) n:returnif len(path) k and sum(path) n:ans.append(path.copy())return# 枚举选哪个for j in range(i, 10):path.append(j)dfs(j 1)path.pop()dfs(1)return ans当然我们可以在判断和是否为n时进行优化 在dfs中传入target参数每选一个数字 j 就把target减去 j code
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:ans []path []def dfs(i, t):if len(path) 10 - i k:returnif t 0:returnif len(path) k and t 0:ans.append(path.copy())returnfor j in range(i, 10):path.append(j)dfs(j 1, t - j)path.pop()dfs(1, n)return ans实战演练 括号生成 https://leetcode.cn/problems/generate-parentheses/
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2
输入n 1 输出[“()”]
提示 1 n 8
思路 将选理解为填左括号, 不选理解为填右括号 题解
class Solution:def generateParenthesis(self, n: int) - List[str]:ans []path []def dfs(i, left, right):if i 2 * n:ans.append(.join(path))return# 左括号数量不能超过nif left n:path.append(()dfs(i 1, left 1, right)path.pop()# 右括号数量不能超过左括号数量if right left:path.append())dfs(i 1, left, right 1)path.pop()dfs(0, 0, 0)return ans总结 剪枝是一种优化技术用于提前终止那些不可能找到解的搜索路径从而提高算法效率。 而组合型回溯问题常常与剪枝相结合 END 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
