coins

coins.cpp

// Input `n`: number of coin_types
// Input `X`: the wanted sum

int coin_types = { ... };

const int32_t TRASH = 2 << 24; // guaranteed greater than X
std::vector<int32_t> coin_count(TRASH, X);

for (int x = 1; x <= X; x++) {
    for (int c = 0; c < n; c++) {
        int coin = coin_types[c];

        if (coin == x) {
            coin_count[x] = 1;
            break;
        }

        // Cannot use this coin
        if (coin > x) { 
            continue;
        }

        int previous_x = x - coin;
        int32_t previous_count = coin_count[previous_x];

        // Could not construct the sum using this coin
        if (previous_count == TRASH) {
            continue;
        }

        if (previous_count + 1 < coin_count[x]) {
            coin_count[x] = previous_count + 1;
        }
    }
}

std::cout << coin_count[X] == TRASH ? -1 : coin_count[X] << std::endl;