# 40 Combination Sum II

Given a collection of candidate numbers (**C**) and a target number (**T**), find all unique combinations in**C**where the candidate numbers sums to**T**.

Each number in**C**may only be used**once**in the combination.

**Note:**

* All numbers (including target) will be positive integers.
* The solution set must not contain duplicate combinations.

For example, given candidate set`[10, 1, 2, 7, 6, 1, 5]`and target`8`,\
A solution set is:

```
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
```

* These I thought this was a really great problem, I wrote about the details of my implementation in my other book *Algorithms and Data Structures B.*

```cpp
struct Key
{
    Key() {};
    Key(const int val, const int iter, const int sum) :
        val(val), iter(iter), sum(sum) {}

    int val, iter, sum;

    bool operator==(const Key &other) const
    {
        return (val == other.val
            && iter == other.iter
            && sum == other.sum);
    }
};

namespace std {
    template <>
    struct hash<Key>
    {
        std::size_t operator()(const Key& k) const
        {
            return ((hash<int>()(k.val)
                ^ (hash<int>()(k.iter) << 1)) >> 1)
                ^ (hash<int>()(k.sum) << 1);
        }
    };

}

struct TreeNode2 {

    TreeNode2(Key key) : 
        key(key) {}
    TreeNode2() {};

    Key key;
    vector<TreeNode2 *> children;
};

class CombinationTree {

public:

    explicit CombinationTree(vector<int> nums, int target) :
        target(target) {

        root = new TreeNode2();
        sort(nums.begin(), nums.end());
        elms = nums;

        for (int i = 0; i < nums.size() && nums.at(i) <= target; i++) {
            Key key = Key(nums.at(i), i, nums.at(i));
            TreeNode2 *base_node = new TreeNode2(key);


            // identifing another subpath within a prebuilt path
            // but the idea is that if we put this path from the root
            // the it will become part of the valid set when
            // seaching all the root to leaf paths
            if (dp_hash_map.find(key) != dp_hash_map.end()) {
                root->children.push_back(dp_hash_map[key]);
                continue; // subtree exist
            }
            dp_hash_map.insert(make_pair(key, base_node));
            root->children.push_back(base_node);
            base_node->children = build_combination_tree(base_node);
        }
    }

    vector<vector<int>> root_leaf_paths(TreeNode2 *root, int target) {
        // good idea to use static parameters here (single reference)
        // just need to make sure to reset on deconstruction
        vector<vector<int>> main;
        vector<int> temp;
        unordered_set<string> unique_paths;
        string temp_str = "";

        // ignore the root
        for (TreeNode2 *n : root->children)
            root_leaf_paths_rec(n, temp, main, target, unique_paths, temp_str);

        return main;
    }

    static void print_level_order(TreeNode2 *root)
    {
        if (!root) return;
        cout << "Value:Iterator:Accumulative Sum:Number Children" << endl << endl;
        queue<TreeNode2*> q;
        q.push(root);
        q.push(nullptr);

        while (!q.empty()) {
            TreeNode2 *temp = q.front();
            if (temp)
                cout << temp->key.val << ":" << 
                temp->key.iter << ":" << temp->key.sum << ":" 
                << temp->children.size() << "  ";
            q.pop();

            if (temp) {
                for (TreeNode2 *t : temp->children) 
                    if (t) q.push(t);
            }
            else {
                if (!q.empty() && q.front()) {
                    q.push(nullptr);
                    cout << endl;
                }
            }
        }
    }

    TreeNode2 *root;

private:

    vector<int> elms;
    unordered_map<Key, TreeNode2*> dp_hash_map;
    int target;

    vector<TreeNode2*> build_combination_tree(TreeNode2* cur_node)
    {
        // current node attributes
        int cur_iter = cur_node->key.iter;
        int cur_sum = cur_node->key.sum;
        int cur_val = cur_node->key.val;

        vector<TreeNode2*> next_children;

        for (int i = cur_iter + 1; i < elms.size() && cur_sum < target; i++) {

            // if the sub tree exists, then do not bother creating
            // the same subtree for it
            Key key = Key(elms.at(i), i, cur_sum + elms.at(i));
            if (dp_hash_map.find(key) != dp_hash_map.end()) {
                // point to the already developed subtree, and continue.
                next_children.push_back(dp_hash_map[key]);
            }
            else {
                TreeNode2* next_node = new TreeNode2(key);
                dp_hash_map.insert(make_pair(key, next_node));
                next_children.push_back(next_node);
                next_node->children = build_combination_tree(next_node);
            }
        }

        return next_children;
    }


    /*
     * Performs traversal of combination tree
     * to collect valid summations
     */
    void root_leaf_paths_rec(TreeNode2 *root, 
        vector<int> &temp, 
        vector<vector<int>> &main, const int target, 
        unordered_set<string> &unique_paths,
        string &temp_str) {

        if (root) {
            temp_str += to_string(root->key.val) + " ";
            temp.push_back(root->key.val);
            if (root->children.empty() && root->key.sum == target
                && unique_paths.find(temp_str) == unique_paths.end()) {

                main.push_back(temp);
                unique_paths.insert(temp_str);

                temp.pop_back();
                pop_back_last_num(temp_str);
                return;
            }
            for (TreeNode2 *t : root->children) {
                if (t) root_leaf_paths_rec(t, temp, main, target, unique_paths, temp_str);
            }
        }
        temp.pop_back();
        pop_back_last_num(temp_str);
    }

    void pop_back_last_num(string &complete_str)
    {
        int iter = complete_str.length() - 2; // ignore first space
        while (iter >= 0 && complete_str.at(iter) != ' ') 
            iter--;

        complete_str = complete_str.substr(0, max(0,iter + 1));
    }
};
```

Some Testing:

```cpp
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
    CombinationTree t = CombinationTree(candidates, target);
    //t.print_level_order(t.root);
    return t.root_leaf_paths(t.root, target);
}

int main(int argc, char **argv)
{
    vector<int> test1 = { 10, 1, 2, 7, 6, 1, 5 };
    print2d(combinationSum2(test1, 8));

    vector<int> test2 = { 1,1,2 };
    print2d(combinationSum2(test2, 3));

    vector<int> test3 = { 1,-2,3,4,-5,6,7,-8,90,-23,45,67,89 };
    print2d(combinationSum2(test3, 6));
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/40-combination-sum-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.