题目描述

给定一个无重复元素的数组 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]
]

解题思路

本题采用了数组拷贝和递归的方法。
首先，在进行数组拷贝时，不能通过简单的赋值，如a=b，这样在b发生变化时，a也会发生同样的变化。在python中可以通过调用copy模块进行数组拷贝，这样在b发生变化时，a会保持不变，即：

import copy
b = copy.copy(a) #浅拷贝
b = copy.deepcopy(a)  # 深拷贝

其次，采用了递归的思想，通过递归不断遍历所有可能的组合，并将满足条件的组合添加到结果数组中。

	 def combine(self, candidates, target, temp, result):
        if sum(temp) == target:
            t = copy.copy(temp)
            t.sort()
            if t not in result:
                result.append(t)
        elif sum(temp) > target:
            return 
        for ele in candidates:
            temp.append(ele)
            self.combine(candidates, target, temp, result)
            temp.pop()

完整代码

import copy
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.combine(candidates, target, [], result)
        return result
        
    def combine(self, candidates, target, temp, result):
        if sum(temp) == target:
            t = copy.copy(temp)
            t.sort()
            if t not in result:
                result.append(t)
        elif sum(temp) > target:
            return 
        for ele in candidates:
            temp.append(ele)
            self.combine(candidates, target, temp, result)
            temp.pop()

本文给出的方法还存在很多可以改进的地方，时间复杂度太高了，目前想到的一个方向是以空间换时间