Close

Printing all K combinations from N numbers

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.
  1. Generate K-Combinations from (N-1) elements.
  2. 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++.

#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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *