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.
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 is used to terminate a function.
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
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]])
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.