## 39. 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:
[
,
[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]
]
``````

Thoughts:

1. Backtracking: can select distinct number repeated times -> so each time for loop start at the passed-in index

Code: T:O(N^2) S: O(N^2)

``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def dfs(res, path, start, target):
if target <= 0 : return
for i in range(start, len(candidates)):
path.append(candidates[i])
if candidates[i] == target:
res.append(list(path))
# pop the tail for next candidate
path.pop()
continue

dfs(res, path, i, target - candidates[i])
# pop the tail for next candidate
path.pop()

return

res = []
dfs(res, [], 0, target)
return res
``````

Code: java with sorting

``````class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
// follow-up: Each number in candidates may only be used once in the combination + there are duplicates.
// follow-up: if(i > start && nums[i] == nums[i - 1]) continue;