Solution using dynamic programming

  • 0
    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:
                    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)
            return self.make_set(dpcombos[-1])
        def make_set(self, ar):
            import itertools
            sorteda = [sorted(a) for a in ar]
            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).

Log in to reply

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