040 combination sum ii
40. Combination Sum II
题目:
https://leetcode.com/problems/combination-sum-ii/
难度:
Medium
Combination Sum 已经AC，做了minor change.
- 现在不需要set化candidates了
- 但是递归的时候index要从i+1开始了
- 要判断combo not in res才append到res中去
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def dfs(remain, combo, index):
if remain == 0 and combo not in res:
res.append(combo)
return
for i in range(index, len(candidates)):
if candidates[i] > remain:
break
dfs(remain - candidates[i], combo + [candidates[i]], i+1)
candidates.sort()
res = []
dfs(target, [], 0)
return res
