# Combination Sum Problem

0 like 0 dislike
102 views

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

Constraints:

• `1 <= candidates.length <= 30`
• `1 <= candidates[i] <= 200`
• Each element of `candidate` is unique.
• `1 <= target <= 500`

## 1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

Best answer

As one can see, the above backtracking algorithm is unfolded as a DFS (Depth-First Search) tree traversal, which is often implemented with recursion.

Here we define a recursive function of backtrack(remain, comb, start) (in Python), which populates the combinations, starting from the current combination (comb), the remaining sum to fulfill (remain) and the current cursor (start) to the list of candidates.

• For the first base case of the recursive function, if the remain==0, i.e. we fulfill the desired target sum, therefore we can add the current combination to the final list.
• As another base case, if remain < 0, i.e. we exceed the target value, we will cease the exploration here.
• Other than the above two base cases, we would then continue to explore the sublist of candidates as [start ... n]. For each of the candidate, we invoke the recursive function itself with updated parameters.
• Specifically, we add the current candidate into the combination.
• With the added candidate, we now have less sum to fulfill, i.e. remain - candidate.
• For the next exploration, still we start from the current cursor start.
• At the end of each exploration, we backtrack by popping out the candidate out of the combination.

class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

results = []

def backtrack(remain, comb, start):

if remain == 0:

# make a deep copy of the current combination

results.append(list(comb))

return

elif remain < 0:

# exceed the scope, stop exploration.

return

for i in range(start, len(candidates)):

# add the number into the combination

comb.append(candidates[i])

# give the current number another chance, rather than moving on

backtrack(remain - candidates[i], comb, i)

# backtrack, remove the number from the combination

comb.pop()

backtrack(target, [], 0)

return results

eg : ans = Solution()

candidates = [2,3,5]

target = 8

ans.combinationSum(candidates, target)

Output-

[

[2,2,2,2],

[2,3,3],

[3,5]

]