<p>Given a collection of candidate numbers (<code>candidates</code>) and a target number (<code>target</code>), find all unique combinations in <code>candidates</code>&nbsp;where the candidate numbers sum to <code>target</code>.</p>

<p>Each number in <code>candidates</code>&nbsp;may only be used <strong>once</strong> in the combination.</p>

<p><strong>Note:</strong>&nbsp;The solution set must not contain duplicate combinations.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> candidates = [10,1,2,7,6,1,5], target = 8
<strong>Output:</strong> 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> candidates = [2,5,2,1,2], target = 5
<strong>Output:</strong> 
[
[1,2,2],
[5]
]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;candidates.length &lt;= 100</code></li>
	<li><code>1 &lt;=&nbsp;candidates[i] &lt;= 50</code></li>
	<li><code>1 &lt;= target &lt;= 30</code></li>
</ul>

class Solution {
public:

    struct Item {
        vector<int> combination;
        int sum;
        size_t index;
        size_t hash = 0;

        Item(int initValue, size_t index) : sum(initValue), index(index), hash(initValue*50) {
            combination.emplace_back(initValue);
        }

        void add(int value, size_t index) {
            sum += value;
            combination.emplace_back(value);
            this->index = index;
            hash += value;
            hash *= 50;
        }

        void print() {
            for (int v : combination) {
                cout << v << " ";
            }
            cout << " sum: " << sum << " index: " << index << endl;
        }
    };

    vector<vector<int>> combinationSum2(vector<int>& candidatesInput, int target) {
        sort(candidatesInput.begin(), candidatesInput.end());
        vector<Item> stack;

        int sum = 0;

        vector<int> candidates;
        for (int i = 0; i < candidatesInput.size(); ++i) {
            int candidate = candidatesInput[i];
            sum += candidate;

            if (candidate > target) {
                continue;
            }

            candidates.emplace_back(candidate);

            if (!stack.empty() && stack.back().combination.back() == candidate) {
                continue;
            }

            stack.emplace_back(Item(candidate, i));
        }

        if (sum < target) {
            return {};
        }

        std::unordered_set<size_t> addedCombinations;

        vector<vector<int>> result;
        while (!stack.empty()) {
            Item item = stack.back();
            stack.pop_back();
            // item.print();
            if (item.sum == target) {
                result.emplace_back(item.combination);
            } else if (item.sum < target) {
                for (size_t i = item.index + 1; i < candidates.size(); ++i) {
                    int candidate = candidates[i];
                    if (item.sum + candidate <= target) {
                        Item newItem = item;
                        newItem.add(candidate, i);
                        auto [iter, res] = addedCombinations.insert(newItem.hash);
                        if (res) {
                            stack.emplace_back(newItem);
                        }
                    }
                }
            }
        }

        return result;
    }
};
17985