Redirecting to
NADOS

Combinations - 1

  Prev   Next

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 <= 10
0 <= ritems <= nboxes
Sample Input 
5
3
Sample Output 
iii--
ii-i-
ii--i
i-ii-
i-i-i
i--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






Video Solution

Code Solution

Run
 
Run
Id Name