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

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]]

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

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

等

完整循环将类似于

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