Solution using dynamic programming

• class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
dpcombos = [[[]]]
for w in range(1, target+1):
combos = []
valid_cands = [cand for cand in candidates if cand <= w]
for d in valid_cands:
if w - d == 0:
combos.append([d])
elif len(dpcombos[w-d][0]) != 0:
combos.extend([[d] + combo for combo in dpcombos[w-d]])
if len(combos) != 0:
combos = self.make_set(combos)
dpcombos.append(combos)
else:
dpcombos.append([[]])
return self.make_set(dpcombos[-1])

def make_set(self, ar):
import itertools
sorteda = [sorted(a) for a in ar]
sorteda.sort()
return list(k for k,_ in itertools.groupby(sorteda))

I am solving this with a dynamic programming approach, getting combos for all 1->target.

Key components is to remove duplicates after finding combos for each target. For that I created a new function make_set(self, ar).

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