Implementation 2

Implementation 2

#include <bitset>
#include <string>
#include <iostream>
#include <random>
#include <vector>
#include <cassert>
#include <iomanip>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <algorithm>
#include <queue>
#include <time.h>

using namespace std;

template<typename T>
inline void print2dnl(vector<vector<T>> &stuffs) {
    int count = 0;
    for (auto i : stuffs) {
        cout << setw(2) << count++ << ":";
        for (auto j : i)
            cout << " " << j << " ";
        cout << endl;
    }
    cout << endl;
}

template<typename T>
inline void printnl(vector<T> &stuffs) {
    for (auto i : stuffs) cout << i << " "; cout << endl;
}

inline void pause() { cin.ignore(numeric_limits<streamsize>::max(), '\n'); }

struct TreeNode2 {
    TreeNode2(int key) :
        index_key(key) {
        visited = false;
    }

    int index_key;
    bool visited;
    vector<TreeNode2 *> children;
};


class CombinationTree {

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

        root = new TreeNode2(-1);
        dp_hash_map.reserve(nums.size());
        sort(elms.begin(), elms.end());

        for (int i = 0; i < elms.size() && elms.at(i) <= target; i++) {
            TreeNode2 *base_node = new TreeNode2(i);
            if (dp_hash_map.find(i) != dp_hash_map.end())
                root->children.push_back(dp_hash_map[i]);
            else {
                dp_hash_map.insert(make_pair(i, base_node));
                root->children.push_back(base_node);
                base_node->children = build_combination_tree(base_node, elms.at(i));
            }
        }
    }

    vector<vector<int>> target_order_traversal()
    {
        // loosely speaking
        const int comb_size = elms.size();

        vector<vector<int>> main;
        vector<int> temp;
        main.reserve(comb_size);

        unordered_set<string> unique_paths;
        string temp_str = "";
        unique_paths.reserve(comb_size);

        for (TreeNode2 *n : root->children)
            target_order_traversal_rec(n, main, temp, unique_paths, temp_str, elms.at(n->index_key));

        return main;
    }

    vector<vector<int>> all_combinations() {
        vector<vector<int>> main;
        vector<int> temp;

        for (TreeNode2 *n : root->children)
            all_combinations_rec(n, main, temp);

        return main;
    }

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

        while (!q.empty()) {
            TreeNode2 *temp = q.front();
            if (temp) {
                if (temp->index_key >= 0) {
                    cout << temp->index_key << ":"
                        << elms.at(temp->index_key) << ":" << temp->children.size() << "  ";
                }
                else cout << "ROOT";
            }

            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;
            }
        }
        cout << endl;
    }

    int space_analyizer_hashed() {
        int count = 0; 
        space_analyizer_hashed(root, count);
        return count ? count - 1 : count;
    }

    int space_analyizer_nonhashed() {
        int count = 0;
        space_analyizer_nonhashed(root, count);
        return count;
    }

    void reset_visited() {
        reset_visited(this->root);
    }

    long long number_of_sum_combinations(int n) {
        // nCr = n! / r! (n-r)!
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += factorial(n) / (factorial(i) * factorial(n - i));
        return sum ? sum - 1 : sum;
    }

    TreeNode2 *root;

private:
    vector<int> elms;
    unordered_map<int, TreeNode2*> dp_hash_map;
    const int target;

    void reset_visited(TreeNode2 *root) {
        root->visited = false;
        for (TreeNode2 *n : root->children)
            reset_visited(n);
    }

    long long factorial(int n) {
        int prod = 1;
        for (int i = 2; i <= n; i++)
            prod *= i;
        return prod;
    }

    vector<TreeNode2*> build_combination_tree(TreeNode2* cur_node, int current_sum)
    {
        int cur_iter = cur_node->index_key;
        vector<TreeNode2*> next_children;

        for (int i = cur_iter + 1; i < elms.size(); i++) {
            if (dp_hash_map.find(i) != dp_hash_map.end())
                next_children.push_back(dp_hash_map[i]);
            else {
                TreeNode2* next_node = new TreeNode2(i);
                dp_hash_map.insert(make_pair(i, next_node));
                next_children.push_back(next_node);
                next_node->children = build_combination_tree(next_node, current_sum + elms.at(i));
            }
        }

        return next_children;
    }

    void target_order_traversal_rec(
        TreeNode2 *root,
        vector<vector<int>> &main,
        vector<int> &temp,
        unordered_set<string> &unique_paths,
        string &temp_str,
        int &current_sum) {

        if (root) { // && current_sum <= target (?)
            int cur_elm = elms.at(root->index_key);
            temp.push_back(cur_elm);
            temp_str += to_string(cur_elm) + " ";

            if (current_sum == target) { // valid
                if (unique_paths.find(temp_str) == unique_paths.end()) { // valid and unique
                    main.push_back(temp);
                    unique_paths.insert(temp_str);
                }
            }
            else {
                for (TreeNode2 *t : root->children) {
                    current_sum += elms.at(t->index_key);
                    if (t) target_order_traversal_rec(t, main, temp, unique_paths, temp_str, current_sum);
                }
            }
        }
        if (!temp.empty()) {
            current_sum -= temp.back();
            temp.pop_back();
            pop_back_last_num(temp_str);
        }

    }

    void all_combinations_rec(TreeNode2 *root,
                              vector<vector<int>> &main,
                              vector<int> &temp) {
        if (root) {
            int cur_elm = elms.at(root->index_key);
            temp.push_back(cur_elm);
            main.push_back(temp);

            for (TreeNode2 *t : root->children) {
                if (t) all_combinations_rec(t, main, temp);
            }
        }
        if (!temp.empty()) temp.pop_back();
    }

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

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

    /*
     * Counts the number of nodes. This helps me ensure that the
     * dp hash table is working as it should. That is, there should
     * only be a linear number of nodes relative to the input array,
     * since every preceeding subtree should always hash to another.
     */
    void space_analyizer_hashed(TreeNode2 *cur_root, int &count)
    {
        if (cur_root) {
            if (!cur_root->visited) {
                cur_root->visited = true;
                count++;
            }
            for (TreeNode2 *n : cur_root->children)
                space_analyizer_hashed(n, count);
        }
    }

    void space_analyizer_nonhashed(TreeNode2 *cur_root, int &count)
    {
        if (cur_root) {
            count += 1;
            for (TreeNode2 *n : cur_root->children)
                space_analyizer_nonhashed(n, count);
        }
    }
};

void comb_sum_test(vector<int>& candidates, int target)
{
    cout << endl;
    clock_t clk;
    int f;
    clk = clock();

    CombinationTree t = CombinationTree(candidates, target);
    clk = clock() - clk;

    const int format_w = 31;
    cout << setw(format_w) << "Input Array: "; printnl(candidates);
    cout << setw(format_w) << "Target Sum: " << target << endl;
    cout << setw(format_w) << "Nodes in graph (non-hashed): " << t.space_analyizer_nonhashed() << endl;
    cout << setw(format_w) << "Nodes in graph (hashed): " << t.space_analyizer_hashed() << endl;

    cout << setw(format_w) << "Tree Construction Time: " << clk << " clicks " << "( " << (float)clk / CLOCKS_PER_SEC << " seconds)" << endl;

    t.reset_visited();
    cout << endl;

    cout << "Full Tree: ";
    t.print_level_order(t.root); cout << endl;

    int max_num_combs = t.number_of_sum_combinations(candidates.size());
    vector<vector<int>> obtained_combs = t.all_combinations();

    cout << setw(format_w) << "Maximum Combinations: " << max_num_combs << endl;
    cout << setw(format_w) << "Obtained Combinations: " << obtained_combs.size() << endl;
    cout << setw(format_w) << "Number of Ignored Elms: " << max_num_combs - obtained_combs.size() << "\n\n";

    cout << "Relavent Combinations: " << endl;
    print2dnl(obtained_combs);

    cout << "Valid Sum Combinations: " << endl;
    print2dnl(t.target_order_traversal());
}

int main(int argc, char **argv)
{
    //vector<int> test0 = { 1,1,2,3,4 };
    //comb_sum_test(test0, 3);

    //vector<int> test1 = { 10, 1, 2, 7, 6, 1, 5 };
    //comb_sum_test(test1, 8);

    //vector<int> test2 = { 0,0,1,2,3,4 };
    //comb_sum_test(test2, 5);

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

    //vector<int> test4 = { 14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12 };
    //comb_sum_test(test4, 27);

    //vector<int> test5 = { 4,1,1,4,4,4,4,2,3,5 };
    //comb_sum_test(test5, 10);

    //vector<int> test6 = { 4,1,1,4,4,4,4,2,3,5,685,2,31,23,5,74,1,3,57,12,24,82,8,1 };
    //comb_sum_test(test6, 73);
}

After Thoughts:

1. Indecies within the element array now serve as a hash key to the element vector rather as well as the associated hash key for dynamically producing subtrees. Construction of the tree is now quadratic to the number of elements within the array.

2. Unfortunately this algorithm is slower than the previous. Because we are referencing previously developed subtrees, the construction of the graph should be $n^2$ relative to the number of elements (observe how each of the red pointers reduce by n-1,n-2... So although construction of the tree is a lot faster, a traversal through the tree carries the same time complexity equivalent to the total sum of combinations. This is where the dead weight is. If I can somehow manage to integrate && current_sum <= target (?) into target_order_traversal_rec- then the complexity would drastically reduce. The idea here is to not recur down into subtrees where the current_sum is already bound to increase and exceed the target (unless the next element is 0 or negative). In addition, because the array is sorted, the search will concluded as fast as possible.

3. Using the iterator of the sequence as a key for hash table proved to be naturally more flexible with the problem we are dealing with. However, it also means that each node could have one of several states that support a current accumulative sum. Because the next base branches from the root are going to very well rely on numbers in the previous branches, it does not become possible to prune the leaf nodes at the bottom (like the previous implementation).

4. I previous thought that the summations were all root to leaf paths. This is not that case. Each node represents and index to the element array. So all possible combinations are just represented as possible root to leaf substructures.

Issues

Although I did not suspect the issue to be when we are construction the tree itself, that is when the cpu hangs for a long time. I believe this is because the construction of the tree was built in a pre order fashion (build the node first, and then form the connections). I believe that a post order traversal would prove to be the solution to this complexity. This is because future nodes rely on the construction of leaf nodes built previously (observe how the bottom nodes always have a fewer number of red pointers).

Task

Build a basic post order construction of a tree - then generalize this to an n-ary tree. Finally implement this function as the main algorithm for root_leaf_paths_rec. Additionally, do not recurse of each child from the root independently as we have here. Build it in one go.