# Combinations - 1 #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are give a number of boxes (nboxes) and number of identical items (ritems).2. You are required to place the items in those boxes and print all such configurations possible.Items are identical and all of them are named 'i'.Note 1 -> Number of boxes is greater than number of items, hence some of the boxes may remain                    empty.Note 2 -> Check out the question video and write the recursive code as it is intended without                    changing signature. The judge can't force you but intends you to teach a concept.`
Input Format
`Input is managed for you`
Output Format
`Check the sample ouput and question video. - means empty box, i means occupied by item.`
Question Video
Constraints
`0 < nboxes <= 100 <= ritems <= nboxes`
Sample Input
`53`
Sample Output
`iii--ii-i-ii--ii-ii-i-i-ii--ii-iii--ii-i-i-ii--iii`

• Editorial

As the items are identical, order will not matter, selection will matter. The total number of ways will be nCr. At level, the boxes will be kept. There will be two option at each level.

Option 1 - Yes - Place the item in the current box

Option 2 - No - Do not place the item in the current box.

Difference between permutation and combination -

Let n = 4, r = 2

Answer for permutation -

1 2 _ _

1 _ 2 _

1 _ _ 2

_ 1 2 _

_ 1 _ 2

_ _ 1 2

2 1 _ _

2 _ 1 _

2 _ _ 1

_ 2 1 _

_ 2 _ 1

_ _ 2 1

Answer for Combination -

i i _ _

i _ i _

i _ _ i

_ i i _

_ i _ i

_ _ i i

As it can be clearly seen in the example, order matters in permutation but not in combination as items are identical in combination.

Formula Used -

2n = nC0  + nC1 + nC2  + ........ + nCn

Total number of ways of placing 1 to n identical items in n boxes is 2^n. At each level there will be 2 calls -

Yes Call - Place item in the current box.

No call - Do not place item in the current box.

Therefore total 2^n calls will be made. When all the boxes are considered and number of YES calls is equal to r, print the sequence.

Signature -

public static void combinations(int cb, int tb, int ssf, int ts, String asf)

cb - current box

tb - total boxes (input n)

ssf - selections so far

ts - total selections allowed (input r)

asf - Sequence so far

Code -

```public static void combinations(int cb, int tb, int ssf, int ts, String asf) {
if (cb > tb) {
if (ssf == ts) {
System.out.println(asf);
}
return;
}

combinations(cb + 1, tb, ssf + 1, ts, asf + "i"); //YES Call
combinations(cb + 1, tb, ssf + 0, ts, asf + "-"); //NO Call
}```

java false

Code Explained -

Boxes is at level. At each level, 2 calls are made. Yes call - place the item in the current box, increase selection so far. No call - do not place the current item in the box, do not increase the selection so far. When the current box will be more than total boxes, base case is reached.

Base Case -

If selections so far is equal to the input r(total selections), it means r items have been placed in n boxes. Print the answer and return.

• Asked in Companies
• Related Topics

Run

Run
Id Name