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的组合。（每个元素可以用无数次）
Solution1: Backtracking
code:
/*
Time: O(n!) factorial, n！=1×2×3×…×n
Space: O(n) coz n levels in stack for recrusion
*/ class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
Arrays.sort(nums); // 呼应dfs的剪枝动作
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(nums, path, result, target, 0);
return result;
} private static void dfs(int[] nums, List<Integer> path,
List<List<Integer>> result, int remain, int start) {
// base case
if (remain == 0) {
result.add(new ArrayList<Integer>(path));
return;
} for (int i = start; i < nums.length; i++) {
if (remain < nums[i]) return; //基于 Arrays.sort(nums);
path.add(nums[i]);
dfs(nums, path, result, remain - nums[i], i);
path.remove(path.size() - 1);
}
}
}