# Combination sum challenge

**Problem statement**

Given a set of candidate numbers (without duplicates) and a target number , find all unique combinations in where the candidate numbers sums to .

The same repeated number may be chosen from unlimited number of times.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

**Sample input**

[2, 3, 6, 7] 7

**Sample output**

[[7], [2, 2, 3]]

**Solution**

class Solution(object): def solve(self, candidates, target, s, combination, result, visited, start): if s == target: key = '-'.join([str(x) for x in sorted(combination)]) if not key in visited: result.append(combination) visited.add(key) return if s < target: for i in range(start, len(candidates)): self.solve(candidates, target, s + candidates[i], list(combination) + candidates[i:i+1], result, visited, i) def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ ans = [] self.solve(candidates, target, 0,[],ans,set(), 0) return ans def main(): solution = Solution() print(solution.combinationSum([2, 3, 6, 7], 7)) print(solution.combinationSum([37,31,46,35,47,21,22,42,33,23,26,41,36,39,48,43,34,24,45,25,29,32,38,44,49], 74)) if __name__ == "__main__": main()