Given a collection of candidate numbers © 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.
Example
Given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
1
2
3
4
5
6
| [
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
|
Solution
(Combination-Sum2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution(object):
def comb_rec(self, c, target, ret, tmp,index):
if target == 0 and tmp not in ret:
ret.append(tmp[:])
return
if target < 0:
return
for i in range(index,len(c)):
if target-c[i] < 0:
return
tmp.append(c[i])
self.comb_rec(c,target-c[i],ret,tmp,i+1)
tmp.pop()
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = sorted(candidates)
ret = []
if not candidates:
return ret
self.comb_rec(candidates,target,ret,[],0)
return ret
|