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

39. 组合总和 - 力扣(LeetCode)

news 来源：原创 2024/9/19 9:10:54

基础知识要求：

Java：方法、集合、泛型、Arrays工具类、for循环、if判断

Python：方法、列表、for循环、if判断

题目：

给你一个 无重复元素 的整数数组 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

思路解析：

这个问题是一个典型的回溯算法问题，可以使用深度优先搜索（DFS）来解决。在DFS的过程中，我们需要维护一个当前路径（即当前组合）以及当前的和。

具体思路如下：

定义一个辅助函数dfs(candidates, target, start, path, res)，其中candidates是候选数组，target是目标和，start是当前搜索的起始位置（保证无重复解），path是当前的组合，res是存储所有解的列表。
在dfs函数中，首先检查当前和是否等于目标和，如果等于，则将当前组合加入结果列表中。
然后遍历候选数组，从start位置开始（允许重复选择），对于每个元素，如果加上当前元素的值不超过目标和，则将该元素加入当前组合，并递归调用dfs函数，传入下一个位置作为新的起始位置。
在递归调用返回后，需要将当前元素从组合中移除（回溯），以便尝试其他可能的组合。

Java代码示例：

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  public class Solution {  public List<List<Integer>> combinationSum(int[] candidates, int target) {  List<List<Integer>> res = new ArrayList<>();  Arrays.sort(candidates); // 排序使得后续可以选择更小的数字  dfs(candidates, target, 0, new ArrayList<>(), res);  return res;  }  private void dfs(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {  if (target == 0) {  res.add(new ArrayList<>(path)); // 添加当前组合到结果中  return;  }  for (int i = start; i < candidates.length; i++) {  if (candidates[i] > target) {  break; // 如果当前数字已经大于目标和，则不需要继续搜索  }  path.add(candidates[i]); // 选择当前数字  dfs(candidates, target - candidates[i], i, path, res); // 注意起始位置仍然是i，因为允许重复选择  path.remove(path.size() - 1); // 回溯，移除当前数字  }  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] candidates = {2, 3, 6, 7};  int target = 7;  List<List<Integer>> combinations = solution.combinationSum(candidates, target);  for (List<Integer> combination : combinations) {  System.out.println(combination);  }  }  
}
以上代码将输出：
[2, 2, 3]  
[7]

Python代码示例：

from typing import List  def combinationSum(candidates: List[int], target: int) -> List[List[int]]:  res = []  candidates.sort()  # 排序使得后续可以选择更小的数字  def dfs(start, path, remaining):  if remaining == 0:  res.append(path[:])  # 添加当前组合到结果中  return  for i in range(start, len(candidates)):  if candidates[i] > remaining:  break  # 如果当前数字已经大于剩余和，则不需要继续搜索  path.append(candidates[i])  # 选择当前数字  dfs(i, path, remaining - candidates[i])  # 注意起始位置仍然是i，因为允许重复选择  path.pop()  # 回溯，移除当前数字  dfs(0, [], target)  return res  # 示例  
candidates = [2, 3, 6, 7]  
target = 7  
print(combinationSum(candidates, target))以上代码将输出：
[2, 2, 3]  
[7]