> For the complete documentation index, see [llms.txt](https://bhabs.gitbook.io/prepbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bhabs.gitbook.io/prepbook/coding/combination-sum.md).

# Combination Sum

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**s ame** 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.

For example, given candidate set`[2, 3, 6, 7]`and target`7`,\
A solution set is:

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

```
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        retList = []
        if not candidates:
            return []
        if not target:
            return []

        self.combinationSumHelper(candidates, target, retList, [], 0)
        return retList

    def combinationSumHelper(self, candidates, target, retList, curList, start):

        #res = 0
        #print 'curList: ', curList, ' target: ', target
        if target < 0:
            return

        if target == 0:
            # Note: remember to copy over the curList using the [:] slicing technique for lists
            retList += [curList[:]]
            #print 'retList: ', retList
            return

        for idx in xrange(start, len(candidates)):
            elem = candidates[idx]
            # Note: Two ways of doing, either make a new list or if the same list is used then do a pop()
            #       after it returns

            #newList = curList + [elem]
            #print 'newList: ', newList
            #self.combinationSumHelper(candidates, (target - elem), retList, newList, idx)

            curList += [elem]
            self.combinationSumHelper(candidates, (target - elem), retList, curList, idx)
            curList.pop()
```