Backtracking: You are given an array with repeated elements and a key element, find all unique combination to the key

Problem Statement:

You are given an array with repeated elements, and a key element.

You need to return the unique combination in that array where the sum is equal to the target.

Example

Input: array = [2,5,2,1,2], key = 5
Output:
[
[1,2,2],
[5]
]

Solution

This problem can be solved by backtracking.

One thing to take care of the duplicates.

For that we will use sets and then at the end we copy it back to 2D vector.

Solution in C++

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

using namespace std;

vector<vector<int> >final_ans;
set<vector<int> >ans;
vector<int> temp;

void backtracking(vector<int>& candidates, int target, set<vector<int> >&ans, vector<int> &temp, int start)
{
  if(target == 0)
  {
      ans.insert(temp);
      return;
  }
  
  for(int i=start; i<candidates.size() && target >= candidates[i]; i++)
  {
      temp.push_back(candidates[i]);
      backtracking(candidates, target - candidates[i], ans, temp, i+1);
      temp.pop_back();
  }
}
vector<vector<int>> get_combination_sum(vector<int>& candidates, int target) 
{
  sort(candidates.begin(), candidates.end());
  backtracking(candidates, target, ans, temp, 0);
  for(auto i : ans)
      final_ans.push_back(i);
  return final_ans;
}

int main()
{
   std::vector<int> array = {10,1,2,7,6,1,5};
   int key = 8;

   vector<vector<int> > result = get_combination_sum(array, key);

   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 1 6
1 2 5
1 7
2 6