蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Combination Sum 组合总和

发表于 更新于 分类于 阅读次数： Valine：

题目大意

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

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

解题思路

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

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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

总结

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

1
Line 15: RuntimeError: maximum recursion depth exceeded

在数据集：

1
2
[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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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