Partial sum lookup / partial sum set assignment

I have following problem to solve. A开发者_高级运维s as input i have 2 decimal arrays. Sum of elements of both of them is equal. Actuall problem is to assign values from one array to second one by partial sums - if some element from one array is a sum of any number of elements from second array - they should be assigned to each other.

Sample1:

Array1: 25.0, 25.0, 50.0, 50.0 Array2: 50.0, 100.0

Expected result: 50.0 is sum of 25.0 and 25.0, 100.0 is a sum of 50.0 and 50.0

(0->0,1; 1->2,3)

Sample2:

Array1: 20.0, 70.0, 80.0, 130.0 Array2: 100.0, 200.0

Expected result: 100 = 20+80, 200 = 70+130 (0->0,2; 1->1,3)

Idea is to return assigned array element indexes and return as less assingments as possible.

---

This is called the subset sum problem.

Unfortunately this is NP-complete, meaning you have to check all possible combinations.

However, if your problem is only has a small quantity of partial sums (such as your examples) then brute force away.

---

Moron is correct, not all NP-complete problem require checking all possible combinations.
However I believe subset sum is one that does.