Subsetting a list to add up to elements in another list

Question

Does anyone have some thoughts on elegant code and math using python to solve the following problem?

I have two lists of numbers:

A=[83.4,108,-240.2]
B=[10.3,96.7,-5.5,-20.4,30.9,2.1,-6.1,51.5,37.7,-25,-10.7,-250.4,-14.2,56.4,-11.5,163.9,-146.6,-2.6,7.9,-13.2]

I know that the B can be divided into three lists that contain elements of B such that the three lists together contain all of the elements in B but the three lists have no overlapping elements. The sum of these three lists will add up to the three elements in A.

I can do the brute force method, which is to create all possible combinations of the elements of B into three sets, but the number of possibilities blows up very quickly with the number of elements in B. I've also looked at the knapsack problem, but that seems to require only positive values.

Answer 1

This is indeed a variant of the subset sum problem:

In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s?

---

Proof that it's NP-complete:

The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it.

It is in NP because it can be verified in polynomial time: given a potential solution, simply add up the numbers in the subsets and see if they correspond to the numbers in A. And, you can reduce the subset problem to this problem in polynomial time: Given set x and target sum s, let A = [s, sum(x) - s] and B = x.

---

It being NP-complete, there is no way to solve this quickly in the general case, using Python or otherwise:

Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.