【LeetCode】0039 组合总数

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

# -*- coding:utf-8 -*-

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i, tmp_sum, tmp):
            """
            回溯法
            :param i: 当前选择的索引
            :param tmp_sum: 当前已选择所有数的和
            :param tmp: 当前已选择数的列表
            :return:
            """
            if tmp_sum > target or i == n:
                return
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i, n):
                if tmp_sum + candidates[j] > target:
                    break
                backtrack(j, tmp_sum + candidates[j], tmp + [candidates[j]])
        backtrack(0, 0, [])
        return res
if __name__ == '__main__':
    candidates = [2, 3, 6, 7]
    target = 7
    print(Solution().combinationSum(candidates, target))

思路：回溯法，十分类似于0037那个解数独，说起来其实也是类似于穷举了。

先依次对列表排序，依次选定数字直到和大于target然后回溯，这样一直回溯，要么所有的数字都被选完，要么和等于target放入res列表。