6/23/2017 - 4:46 PM

## 40. Combination Sum II

1. Combination Sum II
``````class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.res = []
self.cur = []
candidates = sorted(candidates)
# Sort candidates first.
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
preNum = -1 # Use preNum to track the previous number.
for curIdx in range(startIdx,len(nums)):
curNum = nums[curIdx]
if curNum == preNum: # If curNum is the same as preNum, e.g. `1` in [1,1,2...].
continue
self.cur.append(curNum)
self.backtracking(nums, curIdx+1, 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]
preNum = curNum # curNum becomes preNum``````

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

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set `[10, 1, 2, 7, 6, 1, 5]` and target `8`, A solution set is:

``````[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
``````