基础知识要求：
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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同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]