当前位置：首页 > news >正文

LeeCode题库第三十九题

news 2025/9/8 9:22:00

39.组合总和

项目场景：

给你一个 无重复元素 的整数数组 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 <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

问题描述

本题可以利用递归，先将candidate数组排序，递归过程中，如果剩下的数字left为0则添加此时的路径，如果此时i已经为candidate数组最后一个元素或者剩下的数字left小于此时的candidate数组元素，则回退return。递归过程中先不断递归使得candidate最大，如果符合则将此时对应candidate数组的元素加入到path中，继续递归left，否则就pop掉此时的元素，继续进行遍历。

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:       candidates.sort()ans=[]path=[]def dfs(i:int,left:int)->None:if left==0:ans.append(path.copy())returnif i==len(candidates) or left<candidates[i]:return dfs(i+1,left)path.append(candidates[i])dfs(i,left-candidates[i])path.pop()dfs(0,target)return ans

本题提交情况。