39.md

题目地址

https://leetcode-cn.com/problems/combination-sum/

解答

def combinationSum(candidates, target):
    """
        组合总和

        1.排序
        2.target和c取余
    """
    candidates.sort()
    result = []
    n = len(candidates)
    for i in range(n):
        c = candidates[i]
        if i > 0 and c == candidates[i - 1]:
            continue
        if target % c == 0:
            result.append([c] * (target // c))
        for k in range(1, target // c):
            temp = [c] * (target // c - k)
            res = combinationSum(candidates[i + 1:], target % c + k * c)
            if res:
                for r in res:
                    result.append(temp + r)

    return result