[Leetcode][python]Combination Sum/组合总和

╰+哭是因爲堅強的太久メ 2022-06-08 05:26 127阅读 0赞

## 题目大意 ##

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

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

## 解题思路 ##

回溯，答案代码是从小到大，我一开始的思路是从大到小，然后就递归次数过多…..

## 代码 ##

从小到大，将candidates的数字逐步加入，一旦超过target就将candidates切片后再加

class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            if not candidates:
                return []
            candidates.sort()
            result = []
            self.combination(candidates, target, [], result)
            return result
    
        def combination(self, candidates, target, current, result):
            # print candidates
            if current:
                # print current
                s = sum(current)
            else: 
                s = 0
            if s > target:
                return 1
            if s == target:
                result.append(current)
                return 1
            if s < target:
                for i, v in enumerate(candidates):
                    flag = self.combination(candidates[i:], target, current + [v], result)
                    if flag == 1:
                        break

## 总结 ##

这是我已开始写的，最后报错是：

Line 15: RuntimeError: maximum recursion depth exceeded

在数据集：

[92,71,89,74,102,91,70,119,86,116,114,106,80,81,115,99,117,93,76,77,111,110,75,104,95,112,94,73]
    310

说明前面的数据集对了，我觉得写的应该没问题了，应该是递归次数过多的问题，有空看下。

class Solution(object):
        result_list = []
        def combine(self, i, temp, target, candidates):
            # print 'start:', temp
            if i >= 0:
                temp.append(candidates[i])
                print temp, 'this:', candidates[i], 'sum:', sum(temp)
                if sum(temp) == target:
                    self.result_list.append(temp)
                    return self.combine(candidates.index(temp[0])-1, [], target, candidates)
                elif sum(temp) > target:
                    temp.pop()
                    return self.combine(i-1, temp, target, candidates)
                else:
                    return self.combine(i, temp, target, candidates)
            else:
                # print(temp)
                if temp == []:
                    return
                cut = candidates.index(temp[-1]) - 1
                # print 'daodi', cut
                temp.pop()
                return self.combine(cut, temp, target, candidates)
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            i = len(candidates) - 1
            candidates.sort()
            self.combine(i, [], target, candidates)
            return self.result_list