Categories
Mastering Development

Find all SUBSETS of a 1D array that have a specified number of UNIQUE elements (n) AND a specified sum (s)

Consider a 1D numpy array and two constants as shown:

import numpy as np

arr = np.arange(60)

n = 5
s = 120

arr is always of the form [0,1,2,3,4, … 59,60] for example.

QUESTION: From a 1D array (arr), I need to find all subsets exactly n UNIQUE elements that have a specified sum s.
A solution could start like:

          [[2, 10, 26, 35, 47], 
           [9, 14, 15, 40, 42],
           etc...

I have shown the row elements in order. This would be nice, but it is not required. (ie: combinations, not permutations)

Currently, I handle this computation in an SQL variant by using a cross-product of identical tables, each holding the elements of arr.
This works, but is VERY slow, especially if n gets as large as 12 or so.

Is there a way to efficiently and quickly do this in Python/Numpy?

Leave a Reply

Your email address will not be published. Required fields are marked *