首页 > 代码库 > [LeetCode] Add to List 39. Combination Sum Java
[LeetCode] Add to List 39. Combination Sum Java
题目:Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7]
and target 7
,
A solution set is:
[ [7], [2, 2, 3] ]
题意及分析:给出一个数组和一个目标量target,求出由数组元素组成的数组和等于target的所有可能(数组中的元素可以复用),数组所有元素都为正整数,不能包含相同的数组。这道题要求出所有可能,所以可以使用回溯的方法。我们用一个start变量存储子数组开始的位置,用int remian保留target减去当前求值数组的和,这样我们就可以转化为 在start和candidates.length-1中求 和等于target的数组。理解不够深入,讲得不是很清楚,具体可以看一下代码。。
代码:
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); List<Integer> array= new ArrayList<>(); List<List<Integer>> list = new ArrayList<>(); int start=0; int remain=target; backTracking(list,array,candidates,start,remain); return list; } public void backTracking(List<List<Integer>> list,List<Integer> array,int[] candidates,int start,int remain) { if(remain<0) return; else if(0==remain){ //有解 list.add(new ArrayList<>(array)); }else{ for(int i=start;i<candidates.length;i++){ if(i>0&&candidates[i]==candidates[i-1]) continue; //这一步操作主要是去重 array.add(candidates[i]); backTracking(list, array, candidates, i, remain-candidates[i]); //这里注意一下是i,因为元素可以重复利用 array.remove(array.size()-1); } } return; } }
[LeetCode] Add to List 39. Combination Sum Java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。