Find combinations of non-repeating integers summing to a certain number
1 view (last 30 days)
Show older comments
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.
0 Comments
Accepted Answer
John D'Errico
on 2 Oct 2015
Edited: John D'Errico
on 2 Oct 2015
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.
More Answers (0)
See Also
Categories
Find more on Matrices and Arrays in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!