39. Combination Sum
Tags: ‘Array’, ‘Backtracking’
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]
]
Solution
backtracking 模板 67% 100%
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(result, new ArrayList<Integer>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, int remain, int start) {
//结束条件 end condition
if (remain < 0) {
return;
} else if (remain == 0) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]); // 选择
backtrack(result, temp, nums, remain - nums[i], i); // not i+1 because we can reuse same num
temp.remove(temp.size() - 1); // 取消选择
}
}
}