# Find combination of vectors from array that sum up to s

I have an array of $$n$$ $$m$$-dimensional vectors (in my case, they're 27 dimensional). I also have an $$m$$-dimensional vector $$s$$. I want to find all combinations of $$k$$ vectors from my array whose vector sum is equal to $$s$$. How to do this efficiently?

The best I could do is just a brute force which is $$O(n^k)$$ and impossibly slow.

Any help is appreciated.

If $$k$$ if fixed, you cannot do much better than enumerating all subsets of vectors.
$$\binom{n}{k} = \Omega\big((\frac{n}{k})^k\big)$$ is a lower bound in general. Let all input vectors be equal to $$(1,1, \dots,1)$$ and let $$s=(k, \dots, k)$$. There are $$\binom{n}{k} \ge (\frac{n}{k})^k$$ distinct sets of $$k$$ vectors that satisfy your property.
If $$k$$ is part of the input, the problem is NP-complete even when $$m=1$$ (and when we want to know if there's even a single solution). That is, when $$m=1$$, we essentially have a collection of $$n$$ values and our task is to decide if there is a subset of those that sum up to a target $$s$$. This is known as subset sum.
The Wikipedia page lists algorithms that you might be able to adapt to your more general case as well. Also, if $$k$$ is small enough, you might be able to do something better.
• @JhonRayo99 No, just try all $\Theta(n^k)$ subsets; that's a polynomial time algorithm.