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.

Example 1

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

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