Leetcode题库——39.组合总和

@author: ZZQ

@software: PyCharm

@file: combinationSum.py

@time: 2018/11/14 18:23

要求：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,

所求解集为:

[

[7],

[2,2,3]

]

示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

思路：深搜+减枝

注意停止搜索：当和大于target时，结束该条支路的搜索。

注意去重：先对数组排好序，每次都处理当前元素以后的元素。

注意： 存入ans时需要将临时数组拷贝出来，否则ans中的答案会因为temp_ans的改变而一直改变。

import copy
class Solution():
    def __init__(self):
        pass    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        can_len = len(candidates)
        if can_len == 0:
            return []
        ans = []
        temp_ans = []
        temp_sum = 0
        start_index = 0
        self.dfs(temp_ans, temp_sum, start_index, target, candidates, ans)
        return ans    def dfs(self, temp_ans, temp_sum, start_index, target, candidates, ans):
        if temp_sum == target:
            tt_ans = copy.deepcopy(temp_ans)
            ans.append(tt_ans)
            return
        if temp_sum > target:
            return
        for i in range(start_index, len(candidates)):
            temp_ans.append(candidates[i])
            self.dfs(temp_ans, temp_sum + candidates[i], i, target, candidates, ans)
            temp_ans.pop()