# How to partition N numbers into K groups with constraints on the size and sum of each group?

Suppose we are asked to assign $$N$$ numbers into $$K$$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $$k$$ must contain exactly $$n_k$$ elements. The second one is that the sum of all numbers in group $$k$$ must be in the range $$(l_k, u_k)$$. Of course we have $$\sum_{k}^{K}n_k=N$$.

For example, suppose there are 1000 numbers and the sum of the 1000 numbers is 1e5. We need to divide the 1000 numbers into 3 groups, say Group A, B and C. Group A, B and C must contain exactly 600 numbers, 300 numbers and 100 numbers, respectively. Additionaly, the sum of all numbers in Group A must be in the range (1e4, 7e4), the sum of Group B in the range (2e4, 4e4) and the sum of Group C in the range (1e4, 3e4).

Is there an algorithm to solve such a problem?

If the question is instead "Is there an efficient algorithm?" for such a problem, then unless P = NP the answer is no, since the problem includes 3-PARTITION as a special case (take $$n_k=3$$ for all $$k$$ and $$l_1=u_1=...=l_K=u_K$$).
• Yes, I should have said that if there is an efficient algorithm. Brute force is certainly not viable given that $N$ could be very large. The 3-partition problem is indeed a special case, but its contraints are way more restrictive. So the question is, what is the best existing strategy to tackle the more general problem as posted?