leetcode/40. Combination Sum II.py at master · ArniStarkware/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import Counter
from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target + 1)]
        #candidates.sort()
        candidates_count = Counter(candidates)
        dp[0].append([])
        for c,n in candidates_count.most_common():
            for j in range(1,n+1):
                appended = [c for _ in range(j)]
                added = c*j
                for i in range(added, target + 1):
                    for combo in dp[i-added]:
                        if len(combo) == 0 or combo[-1] != c:
                            dp[i].append(combo + appended)
        return dp[target]


candidates = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
target = 10
output = Solution().combinationSum2(candidates,target)
print(output)