怎么做网站的icp备案信息,网站建设项目实训心得,汝州住房和城乡建设网站,网站开发语言本文目录 1 中文题目2 求解方法#xff1a;回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
给定一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #… 本文目录 1 中文题目2 求解方法回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
给定一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
示例
输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]输入: candidates [2], target 1
输出: []提示 1 ≤ c a n d i d a t e s . l e n g t h ≤ 30 1 \leq candidates.length \leq 30 1≤candidates.length≤30 2 ≤ c a n d i d a t e s [ i ] ≤ 40 2 \leq candidates[i] \leq 40 2≤candidates[i]≤40 c a n d i d a t e s candidates candidates 的所有元素 互不相同 1 ≤ t a r g e t ≤ 40 1 \leq target \leq 40 1≤target≤40 2 求解方法回溯法
2.1 方法思路
方法核心
使用回溯算法解决组合问题通过排序和剪枝优化搜索效率维护当前路径和起始位置
实现步骤
1预处理
对候选数组进行排序初始化结果列表
2回溯过程
记录当前路径和剩余目标值从指定位置开始搜索进行剪枝优化维护搜索状态
3状态管理
添加当前数字到路径递归搜索剩余目标回溯删除当前数字继续搜索其他可能
方法示例
输入示例candidates [2,3,6,7], target 7执行过程1. 首先排序本例已排序
2. 开始回溯搜索第一层递归从2开始
- 选择2[2], target5第二层递归- 选择2[2,2], target3第三层递归- 选择2[2,2,2], target1- 回溯到[2,2]- 选择3[2,2,3], target0 找到解- 回溯到[2,2]- 回溯到[2]- 选择3[2,3], target2第三层递归- 选择2[2,3,2], target0 找到解- 回溯到[2,3]- 回溯到[2]
- 回溯到[]
- 选择3[3], target4... 类似过程
- 选择6[6], target1- 剪枝16
- 选择7[7], target0 找到解最终结果[[2,2,3], [2,3,2], [7]]2.2 Python代码
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:# 对候选数组进行排序便于剪枝candidates.sort()# 存储所有符合条件的组合result []def backtrack(target: int, temp_list: List[int], start: int) - None:回溯函数target: 当前还需要的和temp_list: 当前已选择的数字列表start: 本次搜索的起始位置# 如果目标值为0说明当前组合符合要求if target 0:result.append(temp_list[:])return# 从start开始遍历候选数组for i in range(start, len(candidates)):# 剪枝如果当前数字已经大于目标值后面的数字更大直接breakif candidates[i] target:break# 将当前数字加入临时列表temp_list.append(candidates[i])# 递归调用注意target减去当前数字start保持在i因为可以重复使用backtrack(target - candidates[i], temp_list, i)# 回溯移除最后加入的数字temp_list.pop()# 从0开始回溯搜索backtrack(target, [], 0)return result2.3 复杂度分析
时间复杂度 O ( N T / M ) O(N^{T/M}) O(NT/M)N是candidates数组的长度T是目标值targetM是candidates中的最小值 实际复杂度因剪枝而降低 空间复杂度 O ( T / M ) O(T/M) O(T/M) 递归调用栈的深度 3 题目总结
题目难度中等 数据结构数组 应用算法回溯
