40 Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.

Each number inCmay only be usedoncein 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 target8, 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.

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:

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