-
Notifications
You must be signed in to change notification settings - Fork 0
/
LC_Combinational_Sum2.py
61 lines (56 loc) · 1.69 KB
/
LC_Combinational_Sum2.py
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
"""
40. Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
"""
"""
Approach:
1) Take a number and do depth first search.. Do backtrack aswell
2) target is negative.. then cant proceed.
3) if target is zero. Append the past to Answer
4) ensure that smaller numbers are not visited... so as to ensure unique numbers.
"""
import collections
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def rec_sum (past, target, clist, ccount, Ans):
if (target < 0):
return
if (target == 0):
Ans.append(past)
return
for item in clist:
if past and past[-1] < item:
continue;
if (ccount[item] > 0):
ccount[item] -= 1
rec_sum ( past +[item], target-item, clist, ccount, Ans)
ccount[item] += 1
ccount = collections.Counter(candidates)
Ans = []
rec_sum ([],target,set(candidates),ccount,Ans)
return (Ans)