-
题目描述:
-
给你一个 无重复元素 的整数数组
candidates
和一个目标整数target
,找出candidates
中可以使数字和为目标数target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。对于给定的输入,保证和为
target
的不同组合数少于150
个。-
-
-
-
解题思想 :
- 解题思想是使用回溯法(backtracking)。回溯法是一种递归搜索的方法,在搜索过程中不断尝试可能的解,并在不满足条件时进行回退。具体来说,该算法通过递归地尝试每个候选数字,并在满足条件时将当前的组合添加到结果列表中,然后继续递归搜索下一个数字。当搜索到的数字之和等于目标值时,将该组合添加到最终的结果列表中。在搜索过程中,通过对当前数字的多次使用来生成所有可能的组合。
-
解题步骤 :
-
-
编写主函数和递归函数:
- 创建一个主函数,用于初始化算法的输入参数,并调用递归函数。
- 编写一个递归函数,用于搜索所有可能的组合并将它们添加到结果列表中。
-
递归函数的参数:
- 结果列表:用于存储所有有效的组合。
- 临时列表:用于暂时存储当前的组合。
- 候选数字数组:提供可供选择的数字。
- 剩余目标值:表示还需要凑齐的数字之和。
- 起始索引:表示从候选数字数组的哪个位置开始搜索,避免重复搜索已经搜索过的数字。
-
递归函数的终止条件:
- 如果剩余目标值小于0,则说明当前组合无效,直接返回。
- 如果剩余目标值等于0,则将当前临时列表添加到结果列表中,并返回。
-
递归函数的核心逻辑:
- 遍历候选数字数组,从起始索引开始逐个尝试添加数字到临时列表中。
- 在每次递归调用后,需要将添加的数字从临时列表中移除,以便尝试其他可能的组合。
-
主函数中的调用:
- 在主函数中初始化候选数字数组和目标值,并调用递归函数。
- 输出最终的结果列表。
-
注意事项:
- 在递归调用时,起始索引的更新:为了避免重复搜索已经搜索过的数字,需要将起始索引传递给下一层递归函数,并从该索引开始遍历候选数字数组。
- 在递归调用后,需要将添加的数字从临时列表中移除,以便尝试其他可能的组合。
-
以下是代码实现 :
-
import java.util.*;public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();des(result, new ArrayList<>(), candidates, target, 0);return result;}private void des(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {if (remain < 0) return;if (remain == 0) {result.add(new ArrayList<>(tempList));return;}for (int i = start; i < candidates.length; i++) {tempList.add(candidates[i]);des(result, tempList, candidates, remain - candidates[i], i); // 注意这里的 start 是 i,而不是 i + 1,因为一个数字可以使用多次tempList.remove(tempList.size() - 1);}}public static void main(String[] args) {Solution solution = new Solution();int[] candidates = {2, 3, 6, 7};int target = 7;List<List<Integer>> result = solution.combinationSum(candidates, target);System.out.println(result);} }
-
以上是本篇博客的全部内容, 感谢观看
-