Last Updated: 21 Dec, 2021

Combinations

Moderate

Asked in companies

Solve now

Problem statement

Ninja has ‘N’ beautiful paintings labeled from 1 to N.He has to go to an exhibition to showcase ‘K’ paintings. Now, he is confused about which combinations of paintings he should choose.He wants to make all possible combinations of these ‘N’ paintings. Can you help Ninja to make all the possible combinations of N paintings?

You are given two integers N and K. Your task is to print return all possible combinations of ‘K’ paintings.

For Example

For the given if N is 4 and K is 3,the possible combinations are [1,2,3] , [1,2,4] , [2,3,4],[1,3,4] .

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’.

Output Format:

For each test case, print all the possible combinations in each line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 20.
1 <= K <= N.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will define a recursive function REC(‘IDX’, ’N’, ’K’, ’CUR’, ’ANS’) that will form all the possible combinations.IDX represents the current painting number.N represents the total number of paintings. K represents the number of paintings left to be added to the ‘CUR’ combinations and ‘ANS’ will store all possible combinations.

Base Cases:

If K is greater than (N-IDX+1), it implies that we have insufficient painting left to add them into the current combination. So return.

If K is equal to 0, it implies that the CUR combination is completed. Add that combination to ‘ANS’.

For each call, we have two choices either to add the ‘IDX’ picture into the combination or skip the ‘IDX’ painting.

Algorithm:

Declare REC(‘IDX’, ’N’, ’K’, ’CUR’, ’ANS’) function:
- If K > (N-IDX+1) :
  - Insufficient painting left.
  - Return.
- If K is equal to 0:
  - Insert ‘CUR’ into ‘ANS’.
  - Return.
- Call REC(IDX + 1, N , K ,’CUR’ ,ANS) {Not including the IDX painting.}
- Insert ‘IDX into CUR.
- Call REC(IDX + 1, N , K - 1 ,’CUR’ ,ANS) {Including the IDX painting.}
Declare a variable array of arrays ‘ANS’ to store all the combinations.
Declare an empty array ‘CUR’.
Call REC(1, N, K,’ CUR’, ANS)
Return the ‘ANS’ list containing all the possible combinations.

Solve now

02 Approach

In this approach, we will first declare an array ‘CUR’ of size ‘K’ and set all the values to 0. Then we will iterate the array using i from 0 to K-1 and set values as 1,2,3…K. When we reach the index K-1, it implies one combination. is completed. If the value of any index exceeds ‘N‘, we will jump back to the previous index and increase its value to create a new combination.

Algorithm:

Declare a variable array of arrays ‘ANS’ to store all the combinations.
Declare an array ‘CUR’ of size ‘K’.
Set all values of ‘CUR’ to 0.
While i is greater than or equal to 0.
- Set CUR[i] as CUR[i] + 1.
- If CUR[i] is greater than ‘N’:
  - Jump back to the previous index.
  - Set i as i-1.
- Else:
  - If i is equal to ‘K’ - 1:
    - One combination is complete.
    - Insert ‘CUR’ into ‘ANS’.
  - Else:
    - Jump to the next index.
    - Set i as i+1.
    - Set CUR[i] as CUR[i-1].
Return ‘ANS’ .

Solve now