[f]izzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Combination sum challenge

Sharing is caring!

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

The same repeated number may be chosen from $C$ 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)
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()
```