You are given ‘k’ and ‘n’ and you have to do the following:-
Return all possible combinations of arrays whose elements sum is equal to ‘n’, and you can use only elements in the range '1' to '9' inclusive, and you can use each element at most once, and the size of the combination should be exactly ‘k’.
If there is no combination, return an empty array.
It should be noted that the 2-D array should be returned in sorted order, meaning the lexicographically smaller array should come first.
Also, at each index of the 2-D array, the elements present in the array present at that index should be in sorted order.
Two combinations are called different if an element is in one combination and not in another.
Also, in the output, you will see the 2-D array returned by you.
Input: ‘k’ = 2, ‘n’ = ‘5’
Output: [[1, 4], [2, 3]]
Sample Explanation: 1 + 4 = 5 and 2 + 3 = 5. Only these two combinations are there, which sum up to n, so the answer is [[1, 4], [2, 3]].
The first line will contain the value of ‘k’.
The second line will contain the value of ‘n’.
Return all possible combinations. If there is no combination, return an empty 2-D array.
You don't need to print anything. It has already been taken care of. Just implement the given function.
2
5
1 4
2 3
1 + 4 = 5 and 2 + 3 = 5. Only these two combinations are there which sum upto n so answer is [[1, 4], [2, 3]].
3
8
1 2 5
1 3 4
1 + 2 + 5 = 8 and 1 + 3 + 4 = 8. Only these two combinations are there which sum upto n so answer is [[1, 2, 5], [1, 3, 4]].
The expected time complexity is O(2^k), where k is the given integer.
The expected space complexity is O(k), where k is the given integer.
2 <= k <= 9
1 <= n <= 60
Time Limit: 1 sec
Can you think about some backtracking solution?
We can use the elements in the range [1, 9] and that too each element only once. So the max sum can only be 45. We can do a recursive solution where we will add an element in the combination greater than we add in the last operation in this way will not create a similar combination again also we won’t use the same element twice and in each will add an element if the total sum is <= n if the number of elements in the combination is equal to k and sum is equal to n we will add to ‘ans’ matrix. We will return this matrix after the end of the recursion.
The steps are as follows:-
create(self, i: int, k: int, n: int, temp: List[int], ans: List[List[int]], last: int):
combinationSum3(self, k: int, n: int) -> List[List[int]]:
O( 2^9 ).
We have 9 elements in total and each element can either be there in the combination or not there. So we can either pick an element or not pick the element so we have 2 choices for each element and there are 9 elements.
Hence the time complexity is O( 2^9 ).
O( K ), Where 'k' is the number of elements in each combination.
We will make at most k recursive calls so there will recursive stack size of ‘k’.
Hence the space complexity is O( ‘k’ ).
All tags
Sort by
Interview problems
easy cpp
#include<bits/stdc++.h>
using namespace std;
void tPC(int idx,int t,vector<int> &P,vector<vector<int>> &ans,int k){
if (P.size()==k) {
if (t == 0) {
ans.push_back(P);
}
return;
}
for(int i=idx;i<=9;i++){
if(i>t) break;
P.push_back(i);
tPC(i + 1, t -i, P, ans,k);
P.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> ans;
vector<int> P;
tPC(1,n,P,ans,k);
return ans;
}
Interview problems
C++ || BackTracking || Easy to understand solution
void dfs(int start, vector<int> &temp, int k, int target, vector<vector<int>> &ans){
if(k==0){
if (target == 0) {
ans.push_back(temp);
}
}
for(int i=start; i<10; i++){
temp.push_back(i);
dfs(i+1, temp, k-1, target-i, ans);
temp.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> ans;
vector<int> temp;
dfs(1, temp, k, n, ans);
return ans;
}
Interview problems
Most easiest C++ code
void combi(int ind, int k, int n, vector<vector<int>> &ans, vector<int> &ds)
{
if(ds.size() == k && n == 0)
{
ans.push_back(ds);
return;
}
for(int i = ind; i <= 9; i++)
{
if(n < i) continue;
ds.push_back(i);
combi(i + 1, k, n - i, ans, ds);
ds.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> ans;
vector<int> ds;
combi(1, k, n, ans, ds);
sort(ans.begin(), ans.end());
return ans;
}Interview problems
C++ Recursion
void helperFunction(vector<vector<int>>&ans,vector<int>&tmp,int k,int n,int sum,int indx){
if(indx == 10 || tmp.size() == k){
if (sum == n && tmp.size()==k)
ans.push_back(tmp);
return;
}
tmp.push_back(indx);
helperFunction(ans, tmp, k, n, sum+indx,indx+1);
tmp.pop_back();
helperFunction(ans, tmp, k, n, sum, indx+1);
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>>ans;
vector<int>tmp;
helperFunction(ans,tmp,k,n,0,1);
return ans;
}Interview problems
SIMPLE C++ recursive solution
#include<bits/stdc++.h>
void f(int index , int k , int target , vector<vector<int>>&ans,vector<int>& temp , vector<int>&arr){
if(target == 0 && k==0 ){
ans.push_back(temp);
return ;
}
for(int i = index ; i < arr.size() ; i++){
if(k<0 ) continue ;
if(arr[i]>target) break ;
temp.push_back(arr[i]);
f(i+1,k -1 , target - arr[i] , ans ,temp, arr);
temp.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<int>arr = {1,2,3,4,5,6,7,8,9};
vector<vector<int>>ans ;
vector<int>temp;
f(0,k,n,ans,temp , arr);
return ans ;
}
Interview problems
C++...Recursive Approach...
void solve(int ind, int k, int target, vector<int> &temp, vector<vector<int>> &ans){
if (temp.size() == k) {
if (target == 0) {
ans.push_back(temp);
}
return;
}
for (int i = ind; i <= 9; i++) {
if (target >= i) {
temp.push_back(i);
solve(i + 1, k, target - i, temp, ans);
temp.pop_back();
}
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<int> temp;
vector<vector<int>> ans;
solve(1, k, n, temp, ans);
return ans;
}
Interview problems
C++ | Recursion code
void find(int idx, int sum, int k, int n, vector<int>& op, vector<vector<int>>& ans) {
if (sum == n && op.size() == k) {
ans.push_back(op);
return;
}
if (sum > n || op.size() > k || idx > 9) {
return;
}
for (int i = idx; i <= 9; ++i) {
op.push_back(i);
find(i + 1, sum + i, k, n, op, ans);
op.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> ans;
vector<int> ds;
find(1, 0, k, n, ds, ans);
return ans;
}
Interview problems
Python Working solution - uses recursion
from typing import List
def combinationSum(k, n):
def backtrack(start, k, n, path, res):
if k == 0 and n == 0:
res.append(path)
return
if k == 0 or n == 0:
return
for i in range(start, 10):
if i > n:
break
backtrack(i + 1, k - 1, n - i, path + [i], res)
result = []
backtrack(1, k, n, [], result)
return result
passInterview problems
Easy c++ solution
void solve(int k, int n, vector<vector<int>> &ans, vector<int> output, int idx){
// Base case
if(n == 0){
if(k == 0) ans.push_back(output);
return;
}
// Processing
for(int i=idx; i<=9; i++){
if(i > n) break;
output.push_back(i);
solve(k-1, n-i, ans, output, i + 1);
output.pop_back(); // Backtracking
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> ans;
vector<int> output;
solve(k, n, ans, output, 1);
return ans;
}
Interview problems
C++ Easy and Intuitive Recusive Code
void f(int num, int k, int target, vector<int> list, vector<vector<int>> &res){
if(target==0 && k==0){
res.push_back(list);
return;
}
if(num>9 || target<0 || k<0){
return;
}
for(int i=num;i<=9;i++){
if(i>target) break;
list.push_back(i);
f(i+1,k-1,target-i,list,res);
list.pop_back();
}
}
vector<vector<int>> combinationSum(int k, int n) {
vector<vector<int>> res;
vector<int> list;
f(1,k,n,list,res);
return res;
}