combinationSum

找出数组中所有可以使数字和为目标数的组合,数字可以无限制重复使用。

输入配置

候选数字 (用逗号分隔)

目标和

执行过程

步骤 1 / 25

开始寻找和为7的组合

当前路径

空

当前和

0

目标

7

速度:慢速正常快速超快

候选数字: 2, 3, 6, 7

算法说明

组合总和：使用回溯算法，数字可以重复使用，通过剪枝优化性能。时间复杂度O(n^(t/min))。

函数签名

function combinationSum(candidates: number[], target: number): number[][]

参数

参数名	类型	必填	说明
candidates	number[]	是	候选数字数组(无重复元素)
target	number	是	目标和

返回值

类型	说明
number[][]	所有可能的组合

工作原理

1. 排序: 对候选数组排序,便于剪枝
2. 回溯搜索: 从start位置开始遍历候选数字
   • 选择当前数字
   • 递归搜索(可重复使用,所以传入i而不是i+1)
   • 撤销选择
3. 剪枝优化:
   • 如果sum等于target,找到一个解
   • 如果sum大于target,停止搜索
   • 如果当前数字已大于剩余目标,后续更大,直接break
4. 去重: 通过start参数避免重复组合

时间复杂度: O(n^(target/min))
空间复杂度: O(target/min)