Given two integers n and k , Write a program to return all possible combinations of k numbers out of 1 2 3 ... n .

Problem Note

• Elements in a combination must be in a non-descending order.
• The combinations themselves must be sorted in ascending order, i.e., the combination with the smallest first element should be printed first.
• The combination [1,2] is valid but [2,1] is invalid as 2>1 .

Example 1

Input: n = 3, k = 2 
Output:  
[   
  [1,2],  
  [1,3],
  [2,3]
] 

Example 2

Input: 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]  
]