# LC 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.

# DFS

We basically try to find paths in tree that sum up to target. At the beginning, we pick a number as the root and initialize the total_sum to that number. If total_sum < target, we proceed to “branch off”, recursively calling DFS and adding leaves.

## update solution sets

We update the solution set by appending to sol when the target == 0.

## return

return is used to terminate a function.

## Avoid duplicates

### How does duplicates occur

Duplicates occur because when we branch off the tree, we didn’t exclude the elements used in previous path.
To exclude duplicates, when we are making recursive calls at each level, we make sure each function will

# code

``````    def __init__(self):
self.all_path = []
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.bfs(candidates, 0, target, [])
return self.all_path

def bfs(self, nums, index, target, path):
if target < 0:
return
if target == 0:
self.all_path.append(path)
return
for i in range(index, len(nums)):
self.bfs(nums, i, target - nums[i], path + [nums[i]])
``````

## Exclude duplicates

In the for loop, we append nums[i] to the path. Also, we will let index be i so the paths afterword will only contain nums[i]…nums[end].
This avoids duplicates because any possible combinations that sums to target with nums…nums[i – 1] and nums[i]…nums[end] are already found by the function with index nums[i – 1]. So a start index at i will not add this solution to the path.

Posted on Categories Uncategorized