Solution using dynamic programming


  • 0
    R
    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).


Log in to reply
 

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