6/23/2017 - 4:23 PM

## 39. Combination Sum

1. Combination Sum
``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.res = []
self.cur = []
self.backtracking(candidates,0, target)
return self.res
def backtracking(self, nums, startIdx, target):
# Combine elements from startIdx (including) to the end, to sum up to target.
if target < 0:
return
if target == 0:
self.res.append([each for each in self.cur])
return
for curIdx in range(startIdx,len(nums)):
curNum = nums[curIdx]
self.cur.append(curNum)
self.backtracking(nums, curIdx, target-curNum)
# If same element can occur multiple times, backtracking(,curIdx,)
# if same element can't occur multiple times, backtracking(,curIdx+1,)
del self.cur[-1]``````

https://leetcode.com/problems/combination-sum/#/description

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.

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

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