# Another short Python solution

• Not that fast, but easy to write.

There are only two cases:
use the first item or not use the first

``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
#candidates.sort()
res, n = [], len(candidates)
def dfs(sidx, tgt, path): #sidx is the start index in candidates
if tgt == 0:
res.append(path)
return
if tgt < 0 or sidx >= n: return

dfs(sidx + 1, tgt, path) # do not use first item
dfs(sidx, tgt-candidates[sidx], path + [candidates[sidx]]) # use first item (sidx)
dfs(0, target,[])
return res
``````

• Also, combination sum2 can use the same method with small modification (remove duplicates / cannot use one item twice)

``````class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
res, n = [], len(candidates)
def dfs(sidx, tgt, path): #sidx is the start index in candidates
if tgt == 0:
if path not in res: res.append(path)
return
if sidx >= n or candidates[sidx] > tgt: return

dfs(sidx + 1, tgt, path) # do not use first item
dfs(sidx + 1, tgt-candidates[sidx], path + [candidates[sidx]]) # use first item (sidx)
dfs(0, target,[])
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.