Combination Sum

// C++ program to find all combinations that 
// sum to a given value 
#include <bits/stdc++.h> 
using namespace std; 
  
// Print all members of ar[] that have given 
void findNumbers(vector<int>& ar, int sum, 
                 vector<vector<int> >& res, 
                 vector<int>& r, int i) 
{ 
    // If  current sum becomes negative 
    if (sum < 0) 
        return; 
  
    // if we get exact answer 
    if (sum == 0) 
    { 
        res.push_back(r); 
        return; 
    } 
  
    // Recur for all remaining elements that 
    // have value smaller than sum. 
    while (i < ar.size() && sum - ar[i] >= 0) 
    { 
  
        // Till every element in the array starting 
        // from i which can contribute to the sum 
        r.push_back(ar[i]); // add them to list 
  
        // recur for next numbers 
        findNumbers(ar, sum - ar[i], res, r, i); 
        i++; 
  
        // remove number from list (backtracking) 
        r.pop_back(); 
    } 
} 
  
// Returns all combinations of ar[] that have given 
// sum. 
vector<vector<int> > combinationSum(vector<int>& ar, 
                                            int sum) 
{ 
    // sort input array 
    sort(ar.begin(), ar.end()); 
  
    // remove duplicates 
    ar.erase(unique(ar.begin(), ar.end()), ar.end()); 
  
    vector<int> r; 
    vector<vector<int> > res; 
    findNumbers(ar, sum, res, r, 0); 
  
    return res; 
} 
  
// Driver code 
int main() 
{ 
    vector<int> ar; 
    ar.push_back(2); 
    ar.push_back(4); 
    ar.push_back(6); 
    ar.push_back(8); 
    int n = ar.size(); 
  
    int sum = 8; // set value of sum 
    vector<vector<int> > res = combinationSum(ar, sum); 
  
    // If result is empty, then 
    if (res.size() == 0) 
    { 
        cout << "Emptyn"; 
        return 0; 
    } 
  
    // Print all combinations stored in res. 
    for (int i = 0; i < res.size(); i++) 
    { 
        if (res[i].size() > 0) 
        { 
            cout << " ( "; 
            for (int j = 0; j < res[i].size(); j++) 
                cout << res[i][j] << " "; 
            cout << ")"; 
        } 
    } 
}