Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
This problem can be solved in 2 ways.

1. Iterative

2. Recursion/Backtrack

In the iterative solution, we take a temp array of size “k”.
Then we move to the right index, and start filling the values in that temp array iteratively.
When ever the right index value is greater than “n”, then we move to the left index, and start incrementing the value there.

If we find the right candidates, we shall add it to our final result set.

temp[0] = 1 temp [1] = 0
Moved the index to right and copied the value to the left

temp[0] = 1 temp [1] = 2
Pushing the temp in to the result set

temp[0] = 1 temp [1] = 3
Pushing the temp in to the result set

temp[0] = 1 temp [1] = 4
Pushing the temp in to the result set

temp[0] = 1 temp [1] = 5
temp [i] 5 is greater than n. Hence shifting to left index.

temp[0] = 2 temp [1] = 5
Moved the index to right and copied the value to the left

emp[0] = 2 temp [1] = 3
Pushing the temp in to the result set

temp[0] = 2 temp [1] = 4
Pushing the temp in to the result set

temp[0] = 2 temp [1] = 5
temp [i] 5 is greater than n. Hence shifting to left index.

temp[0] = 3 temp [1] = 5
Moved the index to right and copied the value to the left

temp[0] = 3 temp [1] = 4
Pushing the temp in to the result set

temp[0] = 3 temp [1] = 5
temp [i] 5 is greater than n. Hence shifting to left index.

temp[0] = 4 temp [1] = 5
Moved the index to right and copied the value to the left

temp[0] = 4 temp [1] = 5
temp [i] 5 is greater than n. Hence shifting to left index.

temp[0] = 5 temp [1] = 5
temp [i] 5 is greater than n. Hence shifting to left index.

Solution

/*
* File     : get_combinations.cpp
*/
#include<iostream>
#include<vector>

using namespace std;



vector<vector<int>> solution_iterative(int n, int k) 
{
	vector<vector<int>> result;
	int i = 0;
	vector<int> temp(k, 0);
	while (i >= 0) 
	{
		temp[i]++;

		if (temp[i] > n)
		{
			//temp [i]  is greater than n. Hence shifting to left index
			--i;
		}
		else if (i == k - 1)
		{
			//ushing the temp in to the result set
			result.push_back(temp);
		}
		else 
		{
			//Moved the index to right and copied the value to the left
			++i;
			temp[i] = temp[i - 1];
		}
	}
	return result;
}


void helper(int n, int k, int start,vector<vector<int>>& final_result, vector<int>& temp)
{

	if(k==0)
	{
		final_result.push_back(temp);
		return;
	}
	for(int i=start; i+k-1<=n; i++)
	{
		temp.push_back(i);    //push the combinations
		helper(n,k-1,i+1,final_result,temp);
		temp.pop_back();        //backtrack and pop_back
            
	}
}
vector<vector<int>> solution_backtrack_recursive(int n, int k) 
{
	vector<vector<int>> final_result;
	vector<int> temp;
	int start=1; // we start from 1 because it is 1 to n

	helper(n,k,start,final_result,temp);
	return final_result;
}


int main()
{
	int n = 4;
	int k = 2;

	//vector< vector<int>>result = solution_iterative(n, k);

	vector< vector<int>>result = solution_backtrack_recursive(n, k);


    for (int i = 0; i < result.size(); i++)
    {
    	for (int j = 0; j < result[0].size(); j++)
    	{
    		cout<< result[i][j]<<" ";
    	}
    	cout<<endl;
    }


	return 0;
}

Output:

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