LeetCode 40 Combination Sum II 超出时间限制

Question

我正在学习 LeetCode 40. 组合和 II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

我下面的代码一直有效，直到候选人集合变得太大，然后我返回“超出时间限制”。我认为所有递归都在创建太多循环。我显然可以复制教程来获得答案，但我正在尝试弄清楚如何更新我的代码以使其正常工作，以便更好地理解递归的工作原理。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        answers = []
        strings = []
        total = sum(candidates)
        if total < target:
            return []
        def backtrack(total, array, index):
            if total == 0:
                string = ''
                for each in array:
                    string += str(each)
                if string not in strings:
                    answers.append(array)
                    strings.append(string)
                    return
            if index >= len(candidates):
                return
            for each in range(index, len(candidates)):
                backtrack(total - candidates[each], array + [candidates[each]], each + 1)
                backtrack(total, array, each + 1)
        backtrack(target, [], 0)
        return answers

Answer 1

对候选人进行排序是个好主意，但您没有使用它。你应该只在 total-candidate[i]>0 时回收，在 <0 时中断，在 =0

时中断 return

Answer 2

影响性能的一些问题：

当total变为负数时，继续递归过程是没有用的：只会越来越负数。
第二次调用 backtrack 实现了与 for 循环相同的想法。考虑在循环中 each + 1 的所有可能值都将传递给 backtrack(total, array, each + 1)。但还要注意，在递归树的更深一层，所有这些——除了第一个——都被再次！所以要么删除 backtrack(total, array, each + 1) 要么保留它，然后删除 for 循环。
当两个连续的值相同，并且已经对这两个中的第一个进行了递归调用，用重复的值进行递归调用是没有用的。在那一刻，可供选择的值少了一个，总数是一样的，所以不能从中产生任何新的组合。因此，如果我们使用 for 循环（见上一点），则只对不同的值进行递归调用（它们第一次出现）。

还有这个错误：

用于查找重复结果的字符串连接适用于测试用例，但它有点麻烦，因为数字会粘在一起。例如，当 1, 2, 3 被字符串化时，它变成“123”。但是 1, 23 也会像那样被字符串化，这可能会导致漏报。所以这实际上是 LeetCode 上未检测到的代码中的错误。您可以使用分隔符解决此问题。

以下是您的代码，考虑了这些要点：

class Solution: 
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        answers = []
        strings = []
        total = sum(candidates)
        if total < target:
            return []
        def backtrack(total, array, index):
            if total == 0:
                string = ''
                for each in array:
                    string += "_" + str(each)  # Separate the values
                if string not in strings:
                    answers.append(array)
                    strings.append(string)
                    return
            if index >= len(candidates) or total < 0:  # give up when total becomes negative
                return
            current = -1
            for each in range(index, len(candidates)):
                if candidates[each] != current: # Avoid duplicates
                    current = candidates[each]
                    backtrack(total - current, array + [current], each + 1)
                # Don't make another recursive call here. The for-loop is already skipping candidates
        backtrack(target, [], 0)
        return answers

还有改进的余地。你可以想到以下几点：

您的代码当前检查总和是否大于总和。您可以扩展它，并在递归过程中验证总数不大于 remaining 总和。在开始递归之前，您将准备一个包含所有这些“剩余”总和的列表，然后根据该列表中的相关值检查总数。

strings

if string not in strings 效率不高。 strings.
用一套比较好
您可以创建元组而不是子列表，而不是使用字符串作为标识符。这些是可散列的，因此如果您将它们存储在一个整体集合而不是列表中，您将不会得到重复项。然后在最后你可以将那组元组转换为列表的最终列表。

LeetCode 40 Combination Sum II 超出时间限制

LeetCode 40 Combination Sum II time limit exceeded

python

algorithm

recursion

big-o

backtracking