#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<vector<int> > results;
void combinationSum2(vector<int> &nums, vector<int> &counts, int index, int target, vector<int> result) 
{
    if (target == 0)
    {
        results.push_back(result);
        return;
    }
    
    if (nums.size() == index) return;
    
    int n = nums[index];
    int c = counts[index];
    int canUse = target / n;
    if (c < canUse) canUse = c;
    
    result.resize(result.size()+canUse, n);
    while(canUse > 0)
    {
        combinationSum2(nums, counts, index+1, target-n*canUse, result);
        --canUse;
        result.pop_back();
    }
    
    // skip number in [index] of [nums]
    combinationSum2(nums, counts, index+1, target, result);
}


vector<vector<int> > combinationSum2(vector<int> &num, int target) 
{
    results.clear();
    sort(num.begin(), num.end());
    vector<int> nums;
    vector<int> counts;
    size_t size = num.size();
    int val = 0;
    for (size_t i = 0; i < size; ++i)
    {
        if (val == num[i])
        {
            counts.back() = counts.back()+1;
        }
        else
        {
            val = num[i];
            nums.push_back(val);
            counts.push_back(1);
        }
    }
    
    vector<int> result;
    combinationSum2(nums, counts, 0, target, result);
    
    return results;
}

ostream & operator<<(ostream &out, vector<vector<int> > &vv)
{
    for (size_t i = 0; i < vv.size(); ++i)
    {
        vector<int> &v = vv[i];
        for (size_t j = 0; j < v.size(); ++j)
        {
            out << v[j] << ", ";
        }
        
        out << endl;
    }
    
    return out;
}

int main(int argc, char const *argv[])
{
    int a[] = {10,1,2,7,6,1,5};
    size_t at = sizeof(a)/sizeof(int);
    
    vector<int> va(a, a+at);
    
    combinationSum2(va, 8);
    
    
    cout << results;
    
    
    
    return 0;
}