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.
- Iterative
- Recursion/Backtrack
Solution 1: Iterative approach:
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.
Whenever 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 temp[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 in C++
#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
Vishnu teja
https://www.interviewbit.com/problems/n-digit-numbers-with-digit-sum-s-/
Can u provide the solution for the same type of problem using DP.