• ㊗️
• 大家
• offer
• 多多！

## Problem

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]
]


Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

## Code

class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
helper(candidates, res, target, new ArrayList<Integer>(), 0);
return res;
}

private void helper(int[] nums, List<List<Integer>> res, int target, List<Integer> temp, int start){
if(target < 0) return;
if(target == 0){
return;
}

for(int i = start; i < nums.length; i++){
helper(nums, res, target - nums[i], temp, i);
temp.remove(temp.size() - 1);
}
}
}


N 是 candidates 的数量, T 是 target, M 是 candidates 中的最小值.

• 每一个节点的处理时间是 constant, 那么有多少个节点要处理就是时间复杂度.
• 每个节点会生成 N 个子节点，树的最大深度是 T/M
• N 树的节点个数是 N^(T/M + 1) - 深度+1

• 假设每次都添加最小元素 M, 那么最大深度就是 T/M
• 这个空间复杂度计算并没有考虑结果(result)的个数