Given an array of non repeating numbers and a key, find all the unique combinations in that array, where the sum of those combination is equal to the key.

Input: 
	Array = [2,3,6,7], key = 7,
Output:
[
  [7],
  [2,2,3]
]

Example 2:
 Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Note: The input array is sorted, with no repeated elements.

Here as there is no time constraint we can solve this example with the help of “backtracking” technique.

First, what is backtracking?
Below is the simplest way that I can explain it to you guys.

When solving a problem, we might come to a result that is not acceptable because of a wrong decision.

Then we have to go back to the step where we have made the wrong decision and try something else.

This is called Backtracking.

Example:

Sum  = 1
	Sum = 1 + 1
		Sum = 1 + 1 + 1 
			Sum = 1 + 1 + 1 + 1 (sum is same as key, save the combination, remove the last added number and add with the next number from the array)
			Sum = 1 + 1 + 1 + 2(sum is greater than key, remove the last added number and add with the next number from the array)
Sum = 1 + 1 + 2(sum is same as key, save the combination, remove the last added number and add with the next number from the array)
	Sum = 1 + 2
		Sum = 1 + 2 + 2
Sum = 2
	Sum = 2 + 2 (sum is same as key, save the combination)

The same can be shown pictorially as below:

The green color suggests that the sum of the pattern is equal to the key, hence going back [shown by orange lines]

The red color suggests that the sum is greater than the key, hence going back.

Note: Once we get the exact combination in step 2, we don’t continue, because we know if we continue further, then the total sum will be exceeding the key value. Hence we go back to the previous step.

Our recursion/backtrack function will take 6 parameters as input:

• An array containing the array of integers, for final result

• An array of input set

• An integer having current position

• An integer holding the current_sum

• An integer having “key” value

• An array having current combination of elements

Our backtrack function prototype will look like below:

 void backtrack(vector<vector<int>>& final_result_set , vector<int>& input_set, int current_position, int current_sum, int key, vector<int>& current_combination);

Solution in C++

#include<iostream>
#include <vector>

using namespace std;



void backtrack(vector<vector<int> >& final_result_set , vector<int>& input_set, int current_position, int current_sum, int key, vector<int>& current_combination)
{

	if(current_sum > key || current_position == input_set.size()) return;
        if(current_sum == key){
            final_result_set.push_back(current_combination);
            return;
        }
        
        backtrack(final_result_set, input_set, current_position + 1, current_sum, key, current_combination);
        
        current_combination.push_back( input_set [current_position]);
        
        backtrack(final_result_set, input_set, current_position, current_sum + input_set[current_position], key, current_combination);
        current_combination.pop_back();

}

vector<vector<int> > combinationSum(vector<int>& input_set, int key) 
{
        vector<vector<int> >   final_result_set;
        vector<int>   current_combination;

        backtrack(final_result_set, input_set, 0, 0, key, current_combination);
        
        return final_result_set;
}


int main()
{
    vector<int> input_set;
    input_set.push_back(2);
    input_set.push_back(3);
    input_set.push_back(6);
    input_set.push_back(7);

    int key = 7;
     
    vector<vector<int> > final_set =  combinationSum(input_set, key);

    // If final_set is empty, then
    if (final_set.size() == 0)
    {
        cout << "No possible combinations found";
        return 0;
    }
 
    // print the output
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < final_set[i].size(); j++)
                cout << final_set[i][j] << " ";
            cout << ")";
        }
        cout<<endl;
    }

	return 0;
}

( 7 )
( 2 2 3 )