Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}.
For example consider N = 4, K = 3, the possible combinations are
[
[1, 2, 3]
[1, 2, 4]
[2, 3, 4]
[1, 3, 4]
]
Let us look how to solve this combination problem. This problem can be recursively defined as follows. To generate K-combinations from N elements, we have two possibilities.
- Generate K-Combinations from (N-1) elements.
- Generate (K-1)-Combinations from (N-1) elements and append N to all of them.
Let us simulate this with an example. Assume N = 3, K = 2
Generate 2-Combinations from 2 elements i.e N = 2, K = 2
This will be just one combination i.e [1, 2]
Generate 1-Combinations from 2 elements i.e N = 2, K = 1
[1], [2]
Append 3 to each of them
[1, 3], [2,3]
So there are totally 3 combinations [ [1, 2], [1, 3], [2, 3] ].
Here is the recursive implementation in C++.