首页 > 代码库 > Leetcode39--->Combination Sum(在数组中找出和为target的组合)
Leetcode39--->Combination Sum(在数组中找出和为target的组合)
题目： 给定一个数组candidates和一个目标值target,求出数组中相加结果为target的数字组合；
举例：
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3]]
从举例中可以看出，同一个数字可以使用多次，且结果是唯一的；
解题思路：
我个人感觉该题目一点也不难，其实也是一个递归的过程，当达到递归条件时，就将结果加入结果集；
首先题目没说给的数组有啥特性，因此我先将数组进行了排序，这样在某个点找不着结果，那后面的都比target大，自然也就没有结果了。废话不多说，直接看代码；
代码如下：
1 import java.util.*; 2 public class Solution { 3 public List<List<Integer>> combinationSum(int[] candidates, int target) { 4 List<List<Integer>> LList = new ArrayList<List<Integer>>(); // 最终的结果集 5 if(candidates == null || candidates.length < 1 || target < 1 ) 6 return LList; 7 Arrays.sort(candidates); // 排序，使得不用对相同的结果集计算多次 8 List<Integer> list = new ArrayList<Integer>(); // 临时结果保存 9 combinationSumCore(candidates,list, target, 0, LList); // 核心函数10 return LList;11 }12 public void combinationSumCore(int[] candidates,List<Integer> list, int target, int index, List<List<Integer>> LList)13 {14 for(int i = index; i < candidates.length; i++) 15 {16 if(candidates[i] == target) // 等于，就加入结果集17 {18 List<Integer> result = new ArrayList<Integer>();19 result.addAll(list);20 result.add(candidates[i]);21 LList.add(result);22 }23 else if(candidates[i] < target) // 小于，就继续递归24 {25 List<Integer> result = new ArrayList<Integer>();26 result.addAll(list);27 result.add(candidates[i]);28 combinationSumCore(candidates, result, target - candidates[i], i, LList); // 这边i值不变，是因为当前值可以使用多次29 }30 else // 大于，则后面的数字都大于，因此不可能出现在结果集中31 {32 break;33 }34 }35 }36 }
Leetcode39--->Combination Sum(在数组中找出和为target的组合)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。