python - 在我的“组合总和”解决方案中找不到错误

Question

问题可以在这里找到leetcode。我对我的错误在哪里以及为什么我的解决方案没有产生正确的输出感到头疼。我花了几个小时在这上面，仍然无法理解。任何人都可以帮忙吗？我的问题是在函数的最后两行中的某个地方，_rec我试图说明允许从数组中多次添加相同的项目。

我的解决方案：

class Solution:
    def _rec(self, arr, sums, i, all_arrs):
        if sums == 0:
            all_arrs.append(arr[i+1:])
            return
        
        if sums < 0 or i < 0:
            return

        #we can include current number at index i 
        withi = self._rec(arr, sums-arr[i], i-1, all_arrs) 
        
        #or not include it
        arr_copy = arr.copy()
        arr_copy.pop(i) # since we delete higher indices it won't affect lower indices 
        withouti = self._rec(arr_copy, sums, i-1, all_arrs)
        
        #to account on "The same repeated number may be chosen from candidates unlimited number of times."
        arr.append(arr[i])
        repeati = self._rec(arr, sums-arr[i], i, all_arrs)
        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        final_arr = []
        self._rec(candidates, target, len(candidates)-1, final_arr)
        return final_arr

问题给定一组候选数字（候选人）（没有重复）和一个目标数字（目标），找到候选数字总和为目标的所有唯一组合。

可以无限次地从候选中选择相同的重复编号。

笔记：

所有数字（包括目标）都是正整数。解决方案集不得包含重复的组合。示例 1：

输入：candidates = [2,3,6,7], target = 7, 一个解决方案集是：

[
  [7],
  [2,2,3]
]

示例 2：

输入：候选人= [2,3,5]，目标= 8，解决方案集是：

[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
 

约束：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
Each element of candidate is unique.
1 <= target <= 500


Output
[[7],[2,3,3,2],[3,3,2,2],[2,3,2,2,3,2,2],[3,2,2,3,2,2,2],[7]]

Expected
[[2,2,3],[7]]

注意：我知道它可以通过动态编程进行优化，但我现在只想让递归工作。

标签： pythonalgorithm

Answer 1

而不是总是去数组中的下一个数字，只有在达到或超过目标总和时才去下一个数字。

所以在 2,3,5 和 8 的情况下，你会得到

2 = 2
2+2 = 4
2+2+2 = 6
2+2+2+2 = 8

有答案，现在试试下一个号码

2+2+2+3 = 9

太大了，试试下一个数字

2+2+2+5 = 11

ETC

完整的循环就像

2
2+2
2+2+2
2+2+2+2 met
2+2+2+3 exceeded
2+2+2+5 exceeded
2+2+3
2+2+3+3 exceeded (don't do 2 again since we already tried 2+2+2+3 which would be the same)
2+2+3+5 exceeded
2+2+5 exceeded
2+3
2+3+3 met
2+3+5 exceeded
2+5
2+5+5 exceeded
3
3+3
3+3+3 exceeded
3+3+5 exceeded
3+5 met
5
5+5 exceeded
complete