ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

Backtracking: Find combination sum of k numbers that sum up to n

prodevelopertutorial June 26, 2021

Problem Statement:

You are given two numbers K and N, you need to find all valid combinations of k numbers that sum up to n.

Such that only the numbers 1 to 9 are used and at-most only once.

Example

 

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

Because 1 + 2 + 4 = 7

 

Solution

We will use the concept of backtracking.

We need to get the subset of the numbers.

We need to add an element to the “list”, then current target will be, target= target – num[i].

Since we added one element, then we need to add k-1 elements.

Then we use “sol.pop_back();” for backtracking.

Example:

 

K = 3, n = 9

[1]->[1,2]->[1,2,3]. Since the sum is not 9, we remove the "3" and add "4". 

[1, 2, 4], again the sum is not 9. We repeat the process till we reach [1, 2, 6]. Then we will add to the result.

Now again we go back to previous backtracking, i.e
[1,3]->[1,3,4], fail. [1,4,]->[1,4,5] similarly we will continue.

 

Solution in C++

 

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

using namespace std;

void helper(vector<vector<int>>& result, vector<int> sol, int k, int n) 
{
    if (sol.size() == k && n == 0) 
    { 
      result.push_back(sol); 
      return ; 
    }

    if (sol.size() < k) 
    {
      for (int i = sol.empty() ? 1 : sol.back() + 1; i <= 9; ++i) 
      {
        if (n - i < 0) break;
        sol.push_back(i);
        helper(result, sol, k, n - i);
        sol.pop_back();
      }
    }
}

vector<vector<int>> get_combination_sum(int k, int n) 
{
    vector<vector<int>> result;
    vector<int> sol;
    helper(result, sol, k, n);
    return result;
}

int main()
{
   int k = 3;
   int n = 7;

   vector<vector<int> > result = get_combination_sum(k, n);
   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 4

 

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2022 ProDeveloperTutorial.com