CODEWITHSUNDEEP
algorithmlistmathsumtime-complexity
oamandawi
oamandawi

Reputation: 369

How to find the subset of n-element lists that sums up to a target n-element list?

Given a list of n-element lists, A, and a target n-element list, t, find a set of lists, S, in A, whose lists sum up to t.

Summing up lists, here, is the addition of elements at the same position. For example, the sum of [1 2] + [2 3] + [7 5] is [10 10].

Here is an example of the problem:

n = 4

A = [[1 2 3 4] [0 0 1 0] [1 0 0 1] [2 0 0 0] [3 0 0 2] [3 0 0 1] [0 0 0 1]]

t = [4 0 1 3]

Then, we must find S.

S = [[3 0 0 1] [0 0 0 1] [0 0 1 0] [1 0 0 1]]

Notice that we don't need all the sets of lists that add up to t -- we only need one.

This problem may seem similar to the dynamic programming coin change that return an array.

Obviously, this problem can be done in brute force with time complexity of O(2^n) by going over the power set of A. Is there a more optimal solution? Is there another problem similar to this?

Upvotes: 0

Views: 89

Answers (1)

ardenit
ardenit

Reputation: 3890

Solving your problem is equivalent to solving Subset sum problem, which is NP-complete, so your problem is NP-complete too. It means that your problem can't be solved in polynomial time.

Although, if absolute values of all numbers in your lists are less than M, there is a subset sum problem solution in O(n*M*size(a)) (you just need to modify it to your problem, but it is still exponential relatively to number of bits in numbers and takes a lot of memory, but may be better than brute force in certain cases).

Upvotes: 1

Related Questions