Get the number of combinations to make the target number from a given set of denominations

coin_change.cpp

#include <assert.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using MemoizationTable = std::vector<std::vector<int>>;

/** Utility function to dump the memoization table
 */
void dump_table(const MemoizationTable& t) {
    std::cout << std::endl;
    for (const std::vector<int>& v : t) {
        for (const int i : v) {
            printf("%2d ", i);
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void init(MemoizationTable& t, const std::vector<int>& nums) {
    for (int i = 0; i < t.size(); i++) {
        // Always one combination to make a '0'
        t[i][0] = 1;
    }

    for (int i = 1; i < t.front().size(); i++) {
        t[0][i] = i % nums[0] == 0 ? 1 : 0;
    }
}

void fill_table(const std::vector<int>& nums, MemoizationTable& t) {
    // Look column by column (i.e. vertically)
    for (int j = 1; j < t.front().size(); j++) {
        for (int i = 1; i < nums.size(); i++) {
            if (j < nums[i]) {
                t[i][j] = t[i - 1][j];
            }
            else {
                t[i][j] = t[i - 1][j] + t[i][j - nums[i]];
            }
        }
    }
}

int get_num_combo(const std::vector<int>& nums, const int target) {
    if (nums.size() < 1) {
        return 0;
    }

    std::vector<int> sorted_nums(nums);
    std::sort(sorted_nums.begin(), sorted_nums.end());
    auto new_end = std::unique(sorted_nums.begin(), sorted_nums.end());
    sorted_nums.resize(std::distance(sorted_nums.begin(), new_end));

    MemoizationTable t(sorted_nums.size(), std::vector<int>(target + 1));

    init(t, sorted_nums);

    fill_table(sorted_nums, t);

    // Bottom-right element of the memoization table is the solution
    return t.back().back();
}

bool group_sum(const std::vector<int>& nums, const int target) {
    return get_num_combo(nums, target) != 0;
}

int main() {
    std::vector<int> nums = {101, 42, 1, 6, 20, 15, 1};
    //std::vector<int> nums = {1, 4, 10, 26, 52, 75, 101};

    std::cout << get_num_combo(nums, 0) << std::endl;
    std::cout << get_num_combo(nums, 1) << std::endl;
    std::cout << get_num_combo(nums, 14) << std::endl;
    std::cout << get_num_combo(nums, 42) << std::endl;
    //std::cout << get_num_combo(nums, 42242) << std::endl;

    std::cout << "Starting test" << std::endl;

    assert(group_sum({2, 4, 8}, 10) == true);
    assert(group_sum({2, 4, 8}, 14) == true);
    assert(group_sum({2, 4, 8}, 9) == false);

    std::cout << "Test finished successfully" << std::endl;

    return 0;
}