# Stuck on a combinations algo question

There are x digits and y boxes where y is between 1 and x inclusive. I have to print all the possible digits in boxes (combinations) in any order.

For examples, if x = 5 and y = 2 we can have the following 4 combinations:

1234 5
123 45
12 345
1 2345


Similarly if x = 5 and y = 3

123 4 5
12 34 5
12 3 45
1 234 5
1 23 45
1 2 345


if x = 5 and y = 5 then there is only 1 combination

1 2 3 4 5


Both x and y are variable and I can't figure out even a brute force way of doing this. I have tried using three nested for loops but have no luck.

• Hint: You want to populate $y-1$ spaces between $x$ numbers. Can you use a recursive algorithm – orezvani Mar 17 '17 at 5:45
• You can partition X into Y different parts and then make all different permutation of all the different way to partition for example 5 can be partitioned into 3 parts in 2 ways as 1 2 2 and 1 1 3. Now you can permute this 2 arrays and get all the combinations required. – Deep Joshi Mar 17 '17 at 8:03
• This is a nice programming exercise, which I encourage you to work out on your own, along the lines of orezvani's hint. – Yuval Filmus Mar 17 '17 at 10:52
• Do the numbers look familiar? This is a stars and bars problem. – Thumbnail Apr 17 '17 at 8:54

You can print numbers 1 to $x$ and print $y-1$ spaces between them in a brute force manner. The following algorithm does that:

function enumerate(string str, int s, int t, int y):
/* base case: there is no space left and we print the string */
if (y==0)
string str2 = "";
for i=s to t:
str2.append(i);
print str+str2;
return ;

/* recursive case: add one space and recursively call the function */
for i=s to t:
string str2 = "";
for j=s to i-1:
str2.append(j);
str2.append("~");
if (t-i >= y-1) call enumerate(str+str2, i, t, y-1);


You can call enumerate(str="", s=1, t=5, y=2) to print all combinations of numbers 1 to 5 and 2 spaces between them, which gives you a sorted embedding of numbers 1 to 5 in 3 boxes.

Expanding on orezvani's hint:

If you have x balls and y boxes, how many balls can you put in the first box?

• If there is only one box, you have to put all the balls in it.
• Otherwise, you must leave at least y - 1 to be able to put one in each of the other boxes.

However many you choose, you will be left with a similar problem. Cue recursive function ...