算法 |给定一个数组 [] 和 k，找到子集数和 k 的倍数

Question

给定一个正整数 array[] 和另一个整数 k，我必须找到其和是 k 倍数的子集的数量（sum 是可整除的通过 k).

例如，

array[] = {1, 2, 3, 4}, k = 3

子集是，

1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
2 = 2
2 + 3 = 5
2 + 3 + 4 = 9
3 = 3
3 + 4 = 7
4 = 4

因此，{3, 6, 9} 是 k = 3 的倍数，答案是 3。对于上面的相同数组和 k = 2，答案将是 4 = {6, 10, 2, 4} 如何针对数组大小 100 万.

有效地实现它

Answer 1

这是 Subset Sum Problem, and as the original, it is NP-Complete (Reduction from Partition Problem 的紧密变体。很简单。

可以按照递归公式使用动态规划求解：

D(0,0) = true
D(0,x) = false       x > 0
D(i,x) = false       x < 0
D(i,x) = D(i-1,x) OR D(i-1,x-arr[i])

在这里，当且仅当您可以使用前 i 个元素的子集来构建数字 x.

时，D(i,x) 才为真

这可以使用动态规划高效计算。

完成后，只需计算 i 的值的数量，使得 D(n,k*i) = true

这将花费 O(n*W) 时间，其中 n 是元素的数量，W 是它们的总和。

Answer 2

这似乎是对递归的明确使用。

数组中的每个值

自行测试值

测试剩余数组的所有组合，包括有附加值和无附加值。

Algorithm | Given an array[] and k, find number of subsets sum multiple of k