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++.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
vector<vector<int>> combinations(int n, int k) | |
{ | |
vector<vector<int>> res; | |
if( n == 0 || k == 0 || n < k ) //empty result | |
return res; | |
if( n == k )//only one subset is possible which includes all | |
{ | |
vector<int> r(n); | |
for(int i = 0; i < n; i++ ) | |
r[i] = i+1; | |
res.push_back(r); | |
return res; | |
} | |
else if ( k == 1) | |
{ | |
//n subsets are possible each with one element | |
for(int i = 0; i < n; i++ ) | |
{ | |
vector<int> temp(1,i+1); | |
res.push_back(temp); | |
} | |
return res; | |
} | |
else | |
{ | |
//Generate combination of size k-1 from n-1 elements, | |
//for each combination append last element | |
vector<vector<int>> sub = combinations(n-1,k-1); | |
int i; | |
for( i = 0; i < sub.size(); i++ ) | |
{ | |
sub[i].push_back(n); | |
} | |
res = sub; | |
//Generate combinations of size k from n-1 elements | |
//Append this to the result | |
vector<vector<int>> sub1 = combinations(n-1,k); | |
res.insert( res.end(), sub1.begin(), sub1.end()); | |
return res; | |
} | |
} | |
void printResult(vector<vector<int>> & v) | |
{ | |
int i,j; | |
cout << "[" << endl; | |
for( i = 0; i < v.size(); i++ ) | |
{ | |
cout << "["; | |
for( j = 0; j < v[i].size(); j++ ) | |
{ | |
cout << v[i][j] << ", "; | |
} | |
cout << "\b\b]," << endl; | |
} | |
cout << "]" << endl; | |
} | |
int main() | |
{ | |
vector<vector<int>> r = combinations(4,2); | |
printResult(r); | |
r = combinations(5,3); | |
printResult(r); | |
return 0; | |
} |