CODEWITHSUNDEEP
algorithm
Cesare
Cesare

Reputation: 75

Identical sums of elements in two arrays

I have two arrays of integers v1 and v2 with same length. I want to find the largest subset of elements of v1 for which the sum is identical to that of the corresponding elements in v2. For example, let

v1 = [1 2 3 1] 
v2 = [2 3 1 2]

the sum of the 2nd, 3rd and 4th element is 6 in both arrays so this would be the subset that I am looking for.

Is there a way to compute this?

Thanks a lot in advance. Cesare

Upvotes: 2

Views: 104

Answers (1)

user3386109
user3386109

Reputation: 34829

Compute the deltas, and the problem is reduced to the subset sum problem. In other words, create a third array where each element is the difference between the corresponding elements in the two input arrays.

For example, given the input arrays v1 and v2, create a third array v3 that contains the differences:

       0  1  2  3   <-- index into the array
v1 = [ 1  2  3  1] 
v2 = [ 2  3  1  2]
v3 = [-1 -1  2 -1]

Then any subset in v3 that adds to 0 is a solution. In this example, the solutions are represented by the sets of indexes: {0,1,2}, {0,2,3}, and {1,2,3}.

Upvotes: 2

Related Questions