Combinations

Moderate
0/80
Average time to solve is 45m
8 upvotes
Asked in companies
AmazonFacebookGoogle inc

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] .
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 3
4 1
Sample Output 1:
1 2 3
1 3 4
1 2 4
2 3 4
1
2
3
4
Explanation of sample input 1:
For the first test case,
The possible combinations are [1,2,3] , [1,2,4] , [2,3,4],[1,3,4]. 

For the second test case:
The possible combinations are [1],[2],[3],[4].
Sample Input 2:
2
3 3
4 2
Sample Output 2:
1 2 3
1 2 
1 3
1 4
2 3 
2 4
3 4
Hint

Try to think of a recursive approach.

Approaches (2)
Recursion

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.
Time Complexity

O(2^N ), where ‘N’ is the given number .

 

In this approach, we are finding all the combinations recursively and for each IDX from 1 to N, we are making two recursive calls. Hence, the overall time complexity is O(2^N)

Space Complexity

O(2^N ), where ‘N’ is the given number.

 

In this approach, we are using a recursive function and in the worst case, the number of function calls will be O(2^N). So, a space of 2^N will be stack memory occupied. Hence, the overall space complexity is O(2^N).

Code Solution
(100% EXP penalty)
Combinations
Full screen
Console