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列表。
0 条评论