MATLAB: Find combinations of non-repeating integers summing to a certain number

combinationsintegers

Given a number x, I would like to find all non-repeating combinations of integers in range 1:n that form a vector of length m whose elements sum to x.
For example: x = 9; n = 6; m = 3;
Should return: [4 3 2] [5 3 1] [6 2 1]
This will be used many times with an n ~ 100, and needs to be general for any x or m, so the method should be as efficient as possible.

Best Answer

Using my partitions code...
partitions(9,1:6,1,3)
ans =
   0     1     1     1     0     0
   1     0     1     0     1     0
   1     1     0     0     0     1
A 1 in any row indicates that element appears in the sum.
For a larger problem, here are the set of all solutions with a sum of 100, 3 elements in the sum, from the set 1:60. 423 possible solutions.
sols = partitions(100,1:60,1,3);
size(sols)
ans =
   423    60
partitions can be found on the file exchange.
Of course, it is trivial to create an impossibly large problem, but partitions is reasonably efficient on rationally sized problems.
Related Question