python - 总和可被 k 整除的子序列数

Question

我刚刚为一家公司做了一个编码挑战，无法解决这个问题。问题陈述如下:

给定一个整数数组，找出数组中总和可被 k 整除的子序列的数量，其中 k 是某个正整数。

例如，对于 [4, 1, 3, 2] 和 k = 3，解为 5。[[3], [1 , 2], [4,3,2], [4,2], [1,3,2]]是其和能被k整除的子序列，即current_sum + nums[i] % k == 0，其中 nums[i] 是数组中的当前元素。

我试图递归地解决这个问题，但是，我无法通过任何测试用例。我的递归代码是这样的:

def kSum(nums, k):
    def kSum(cur_sum, i):
        if i == len(nums): return 0
        sol = 1 if (cur_sum + nums[i]) % k == 0 else 0
        return sol + kSum(cur_sum, i+1) + kSum(cur_sum + nums[i], i+1)
    return kSum(0, 0)

这种递归方法有什么问题，我该如何纠正它？我对迭代解决方案不感兴趣，我只是想知道为什么这个递归解决方案是错误的以及我该如何纠正它。

Answer 1

你确定那不是案例测试？例如:

[4, 1, 3, 2], k = 3

有

4+2 = 6, 1+2=3, 3, 1+2+3=6, 4+2+3 = 9

所以，您的功能是正确的(它给了我 5)，而且我没有发现您的功能存在重大问题。