Implementation 1

Implementation 1

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));
    }
};

Testing:

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));
}

After Thoughts: 1. Our dp hash table for the tree should index by just the iterator, and not the sum, iter, and value of a node as I have done here. 2. The dp hash table for the tree should be reserved to N, where N is the size of the array. In addition, the size for the unordered_set<string> in root_leaf_paths_rec should be reserved to the maximum number of possible combinations which is $\sum_{n = 0}^k{nCk}$. 3. Rather than referencing the value within the array directly, it would be simpler and possible more space efficient to instead reference an index to the value within the array. With an array of strings for example, each node can reference an index to the array rather than other copy of the string. This would be simpler in the sense that the pattern that evolves from these index's become more explicit in the construction of the tree. Observe: 4. At one point I considered multi-threading each subtree form the bast root, but because every proceeding subtree is heavily reliant on the hash table - it is best be done linearly. 5. Because our next implementation will index by iterator, the accumulative summation will have to be dynamically produced at run time. This is because now each node will have multiple children and multiple parents, and therefore different relative summations depending on the parent. In other words, we will be transforming this tree into a graph.