Backtracking: Get the k combination from an array of 1 to n

Problem Statement:

You are given 2 integers n and k, you need to return all possible combination of K numbers from the range [1, n]

Example

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Solution

We will use backtracking approach to solve this problem.

We will call a recursion function, everytime we push an element into the vector, we push a bigger number into it.
Then if we push the K number, then we store it in the result, then we push the next bigger element.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<vector>
#include<set>

using namespace std;

void solve(vector<vector<int>>& result,int n,int begin ,int k ,vector<int>& combination)
{
  if(combination.size()==k)
  {
      result.push_back(combination);
      return;
  }

  for(int i=begin ; i<=n ;i++)
  {
      combination.push_back(i);
      solve(result , n , i+1 , k , combination);
      combination.pop_back(); // backtracking part
  }
}

vector<vector<int>> combine(int n, int k) 
{
  vector<int> combination;
  vector<vector<int>> result;
  solve(result , n , 1 , k , combination);
  return result;
}

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

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

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

    return 0;
}

Output:

Result =
1 2
1 3
1 4
2 3
2 4
3 4