Generate Combinations Recursively

Given a list of distinct integers and an integer \(k\), your task is to generate all possible combinations of \(k\) numbers from the given list using recursion. The solution employs a backtracking strategy: choosing an element, recursively generating the remainder of the combination, and then backtracking to try alternative possibilities.

The mathematical formula for the number of combinations is given by \(C(n,k) = \frac{n!}{k!(n-k)!}\), where \(n\) is the total number of elements.

inputFormat

The input is read from standard input. The first line contains space-separated integers representing the list. The second line contains a single integer representing k. If the first line is empty, the list is considered empty.

outputFormat

Print each combination on a new line with the numbers separated by a space. If a combination is empty (which occurs when k is 0), print an empty line. Combinations must be printed in lexicographical order.## sample

1 2 3 4
2

1 2
1 3
1 4
2 3
2 4
3 4