Combination Sum
文章目录
Combination Sum
Given a set of candidate numbers (C) 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. Elements in
a combination (a1, a2, … , ak) must be in non-descending order. (ie,
a1 ≤ a2 ≤ … ≤ ak). 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 number 传入, 每次加入一个数字,就把target number 减去这个数字递归。 当target number == 0 时,说明此时list中的数字的和为target number。 就可以将这组数字加入list里面。 注意可以重复加数字, 所以每次递归传的index就是i。
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(candidates);
int sum = target;
helper(result,list, sum,candidates,0);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> list,int sum, int[] candidates,int index) {
if (sum == 0) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
if (sum < 0) {
break;
}
list.add(candidates[i]);
helper(result,list, sum - candidates[i], candidates,i);
list.remove(list.size() - 1);
}
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论