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

Given an array[] of positive integers and another integer k, I have to find number of subset whose sum is multiple of k(sum is evenly divisible by k).

给定正整数的数组[]和另一个整数k，我必须找到其和为k的倍数的子集的数量（总和可被k整除）。

For example,

例如，

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

Subset sums are,

子集总和是，

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

Thus, {3, 6, 9} are multiple of k = 3 and the answer is 3. For the same array above and k = 2, answer will be 4 = {6, 10, 2, 4} How to implement it efficiently for array size 1 million.

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

2 个解决方案

#1

This is a close variant of Subset Sum Problem, and as the original, it is NP-Complete (Reduction from Partition Problem is trivial).

这是子集和问题的近似变体，并且作为原始，它是NP完全的（从分区问题的减少是微不足道的）。

It can be solved using Dynamic Programming by following the recursive formulas:

它可以通过遵循递归公式使用动态编程来解决：

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

In here, D(i,x) is true if and only if you can use a subset of the first i elements to build the number x.

在这里，当且仅当您可以使用前i个元素的子集来构建数字x时，D（i，x）才为真。

This can be calculated efficiently using Dynamic Programming.

这可以使用动态编程有效地计算。

When you are done, simply count the number of values of i such that D(n,k*i) = true

完成后，只需计算i的值的数量，使得D（n，k * i）=真

This will take O(n*W) time where n is the number of elements, and W is the sum of them.

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

#2

This seems like a clear use of using recursion.

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

for each value in array

对于数组中的每个值

test value by itself

自己测试价值

test all combinations of remaining array, both with value added and without value added.

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

#1