更多精彩内容,请关注【力扣中等题】。
题目
难度:★★★☆☆
类型:数组
方法:回溯法
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解答
方案1:回溯法
我们使用回溯法解决这道题。回溯法的思想是如果不合适,就退回上一步。
我们写一个函数helper,用来实现回溯操作。
输入参数
- 当前要考察的元素所在的下标(index);
- 加到当前为止的和(cur_sum);
- 临时列表(cur_list),用来记录组成当前和cur_sum所使用过的所有加数;
操作流程
- 判断操作是否合法,用来限制操作次数,有两个判断条件:
(1)当前考察的元素所在下标i是否合法,是否出现越界;
(2)当前为止的和cur_sum是否已经超过目标值target,如果已经超过,则没有必要再进行操作。 - 判断是否已经满足条件,即cur_sum是否已经等于目标值target,如果已经相等,则把组成cur_sum的各个加数cur_list加入到结果列表res中。
- 考察在当前和cur_sum中加入当前元素candidates[index]的情况,即:helper(index, cur_sum+candidates[index], cur_list+[candidates[index]])。
- 考察在当前和cur_sum中不加入当前元素的情况,即跳过当前元素,考察下一个元素:
helper(index+1, cur_sum, cur_list)。
回溯法的精髓在于步骤3和步骤4,可以遍历到所有可能的组合情况。有关回溯法的讲解与更多题目,请移步【回溯法综述】
注,这里可以不使用排序,因为数组中的元素是没有重复的。
class Solution:
def combinationSum(self, candidates, target):
"""
:param candidates: List[int]
:param target: int
:return:
"""
def helper(index, cur_sum, cur_list):
"""
:param i: 当前考察的元素
:param cur_sum: 当前和
:param cur_list: 获得cur_sum所用的元素
:return:
"""
# 跳出循环的条件
if cur_sum > target or index == len(candidates):
return
# 如果找到符合条件的子数组,则添加到结果中
if cur_sum == target:
res.append(cur_list)
return
# 考虑当前元素candidates[i]
helper(index, cur_sum + candidates[i], cur_list + [candidates[i]])
# 不考虑当前元素
helper(index+1, cur_sum, cur_list)
candidates.sort()
res = []
helper(0, 0, [])
return res
如有疑问或建议,欢迎评论区留言~