Find all subsets of size K from a given number N (1 to N)

Objective: Given two integers N and K, Write an algorithm to find subsets of size K from the numbers 1 to N. 

Example:

N = 5
K = 3
Output:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

N = 6
K = 5
Output:
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 5, 6]
[1, 2, 4, 5, 6]
[1, 3, 4, 5, 6]
[2, 3, 4, 5, 6]

Approach: Use Recursion

  1. Given N and subset size K.
  2. Start with startNumber = 0, combinationList=null
  3. Iterate through i = startNumber to N.
    • Put i to combinationList.
    • Make a recursive call with startNumber=i+1, K=K-1 and (to process next elements) and combinationList.
    • In tail recursion, backtrack and remove i from the combinationList to find more solutions 
    • Base case: if K=0,  Print combinationList.

Complete Code:

Output:

Given Number: 6, subset size K: 5
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 5, 6]
[1, 2, 4, 5, 6]
[1, 3, 4, 5, 6]
[2, 3, 4, 5, 6]

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: