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

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