69. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解题思路:
考虑两个条件:
- 组合元素可以重复
- 和为 target
递归三要素: - 递归的定义
找到所有和为 target 的组合,放到 result 递归的拆解
递归的出口
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null){
return results;
}
List<Integer> combination = new ArrayList<>();
Arrays.sort(candidates);
recursion(candidates,0,target,combination,results);
return results;
}
// 1. 递归定义
public void recursion(int[] candidates,
int startIndex,
int remainTarget,
List<Integer> combination,
List<List<Integer>> results){
// 3. 递归出口
if (remainTarget == 0){
results.add(new ArrayList<Integer> (combination));
return;
}
// 2. 递归拆解
for (int i = startIndex; i< candidates.length;i++){
if (remainTarget < candidates[i]){
break;
}
if (i!=0 && candidates[i] == candidates[i-1]){
continue;
}
combination.add(candidates[i]);
recursion(candidates,i,remainTarget - candidates[i], combination,results);
combination.remove(combination.size()-1);
}
}
}
请多多指教。
文章标题:69. Combination Sum
本文作者:顺强
发布时间:2019-09-18, 23:59:00
原始链接:http://shunqiang.ml/leetcode-69-combination-sum/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。