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