Recursive solution of ordered Coin Combinations II (CSES)

Question

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

2+2+5
3+3+3
2+2+2+3

The return value is to be printed modulo 10⁹+7.

I am trying to write recursive solution for this.
I came up with this code.

#include<iostream>
#include<vector>
using namespace std;
#define M 1000000007
 
vector<int>arr;
vector<vector<int>>dp;

int solve(int i,int target){
    if(i>=(int)arr.size()) return 0;
    if(target<0) return 0;
    if(target==0) return 1;
    if(dp[i][target]!=-1) return dp[i][target];
    return dp[i][target]=(solve(i,target-arr[i])%M+solve(i+1,target)%M)%M;
}

int main(){
    int n,target;
    cin>>n>>target;
    arr.resize(n);
    dp.resize(n+1,vector<int>(target+1,-1));
    for(int i=0;i<n;++i){
        cin>>arr[i];
    }
    cout<<solve(0,target);
}

but this code is giving time-limit-exceeded. What can I do to improve the performance so that it gets accepted?

Here is an iterative version but I'd like to keep the recursive approach if I can.

Answer 1

Normally I do a design review first, then review the code itself. This time I’m going to switch it around.

Code review

Before I get into review this code, I just have to say that the sample solution code given is… ghastly. Seriously, if someone worked at a software company I owned, and they submitted that kind of code, I’d not only fire them, I’d have them escorted out of the building by security and thrown into a ditch on principle. That code is a crime against humanity.

This code isn’t nearly as horrific as that code, which is a good thing. Do NOT learn to code from crappy examples like that.

Okay, from the top:

#include<iostream>
#include<vector>
using namespace std;
#define M 1000000007

You should really space out your code some more. Whitespace is free; it costs nothing at runtime, and (almost!*) nothing at compile time. And it makes code much easier to read.

(* The “almost” is because, I mean, technically, if you used a billion spaces or newlines, it would take longer for the compiler to read the source code file, obviously. But unless you’re getting absolutely insane with your whitespace like that, a little bit of extra whitespace really doesn’t matter.)

You should never, ever use using namespace std;. Ever. It can introduce subtle bugs, and even if it happens to work now, it could easily break when you upgrade your compiler.

You should never use the preprocessor for constants. Use constexpr.

But there is another problem with the constant, and it is that when you just write an integer literal, the type is int by default. The problem is, the portable range for int is −32,767 to 32,767 (starting from C++20, that is extended to −32,768 to 32,767). 1,000,000,007 is way outside of that range. However, it does fit in the portable range of a long: −2,147,483,647 to 2,147,483,647 (C++20+: −2,147,483,648 to 2,147,483,647). So this constant should be a long:

#include <iostream>
#include <vector>

constexpr auto ??? = 1'000'000'007L;

The one thing left to do is give the constant a name. You shouldn’t use M because ALL_CAPS names should be reserved for the preprocessor. That suggests the name should be m… but that’s a terrible name, especially for a global constant. You should give variables meaningful names… in this case, maybe result_modulo or something like that.

vector<int>arr;
vector<vector<int>>dp;

First, once again there are cryptic names. arr? Really? What is arr? What does it mean? What is it used for? What values does it hold? Pirates?

This vector holds the values of the coins. So… why not call it coin_values?

Second, there’s no reason these should be global variables. Global variables are evil for a number of reasons: they are less efficient, they make code harder to understand (and thus, more likely to be buggy), they make code harder to test (and you are testing your code, aren’t you?), and—in this case—they limit your design options (which I’ll explain in a bit).

And finally, as a general rule, whenever you see a vector-of-vectors… that’s usually a sign of a bad design. There are some situations where a vector-of-vectors makes sense, but virtually all uses you see in the wild are wrong. This usage? Seems very wrong.

int solve(int i,int target){
    if(i>=(int)arr.size()) return 0;
    if(target<0) return 0;
    if(target==0) return 1;
    if(dp[i][target]!=-1) return dp[i][target];
    return dp[i][target]=(solve(i,target-arr[i])%M+solve(i+1,target)%M)%M;
}

Okay, now we get to the meat of the problem.

My first complaint is that there’s not a single comment in the code. This is not acceptable in real code. A code reviewer should not have to reverse-engineer your code to figure out what it’s doing. When I see code with no comments like this, I usually don’t even bother to examine it; I just stamp it “fail”, and move on. You don’t need to explain each and every single line and operation, but you should at least explain the logic of what the function is supposed to be doing. The function’s name is “solve”. Solve what? How? The arguments are “i” and “target”. What are those supposed to be? I mean, I can deduce “target” is the value you want to “solve” for… but what the hell is “i”? That doesn’t even come from the problem; that’s an artifact of your particular solution, so it can only make sense to you.

My second complaint is that the code is almost illegible because it’s so tightly packed together. Use some whitespace! Spread things out a bit! You have five different exit points in this function, but that’s hard to see without carefully examining every line of the code. That’s terrible; it’s begging for bugs to be hidden in the code.

(I strongly suspect that the reason no one else has tried to review this code has to do with the fact that it’s impossible to read, and has not a single comment explaining it. Nobody wants to do a forensic deconstruction of someone’s code just to review it.)

So, first thing I’m going to do, for my own sanity, is spread the function out a bit, and then use better identifiers.

int solve(int i, int target)
{
    if (i >= (int)arr.size())
        return 0;

    if (target < 0)
        return 0;

    if (target == 0)
        return 1;

    if (dp[i][target] != -1)
        return dp[i][target];

    return dp[i][target] = (solve(i, target - arr[i]) % M + solve(i + 1, target) % M) % M;
}

Okay, let’s deal with those globals and the poorly named constant:

int solve(int i, int target, std::vector<int> const& coin_values, std::vector<std::vector<int>> const& dp)
{
    if (i >= (int)coin_values.size())
        return 0;

    if (target < 0)
        return 0;

    if (target == 0)
        return 1;

    if (dp[i][target] != -1)
        return dp[i][target];

    return dp[i][target] = (
        solve(i, target - coin_values[i], coin_values, dp) % result_modulo
            + solve(i + 1, target, coin_values, dp) % result_modulo)
        % result_modulo;
}

Now we need to fix the types. As mentioned earlier, the portable range of int is −32,767 to 32,767 (C++20: −32,768 to 32,767), but the target range is from 0 to 1,000,000. So target can’t be an int. It needs to be a long. The same goes for the coin values.

And then there’s i. What is i? No idea, because there’s no comment explaining it, so I have to guess. It looks like it is supposed to be an index into the coin values array. In C++ indices are unsigned types (I know, that’s not great, but that’s what we’re stuck with). In particular, it should be std::vector<int>::size_type.

So this is probably what the function parameters should be more like:

int solve(std::vector<long>::size_type i, long target, std::vector<long> const& coin_values, std::vector<std::vector<int>> const& dp)

Not sure what to do with dp, because I have no idea what dp is supposed to be for, because, again, no comments explaining anything. 🤷🏼 If I had to guess, dp is being used as some sort of highly inefficient and wasteful memoization or caching scheme. More on that later.

Once you’ve got the types right, you don’t need casts anymore, so if (i >= (int)coin_values.size()) just becomes if (i >= coin_values.size()), as it should be.

But… you might have a bug. Not sure, because the code is not properly commented (you see how often this comes up?), but it sure looks suspicious that you’re making sure i is less-than-or-equal the coin value array size. Now, dp is created to be the size of the coin value array… plus one… so maybe it’s not a problem. Maybe.

So, with some detective work and guessing, this is what I think the first part of your function is doing:

int solve(
    std::vector<long>::size_type i,
    long target,
    std::vector<long> const& coin_values,
    std::vector<std::vector<int>> const& dp)
{
    // ???
    if (i >= coin_values.size())
        return 0;

    // Recursive end condition: Either we've overshot the target, or nailed it
    // exactly.
    if (target < 0)
        return 0;
    if (target == 0)
        return 1;

    // ...

The next if statement is suspicious. It seems to be testing whether this particular solution has already been found. (-1 seems to be a magic number indicating “not solved yet”… again, this would be much easier to understand with some comments!!!)

The reason this is suspicious is because you shouldn’t really be recalculating solutions over and over. That indicates a problem with your algorithm’s design. Even if you bail before recalculating, the fact that the function was recalled to recalculate in the first place means you’re wasting time.

The last chunk of the function can be simplified quite a bit, to:

int solve(
    std::vector<long>::size_type i,
    long target,
    std::vector<long> const& coin_values,
    std::vector<std::vector<int>> const& dp)
{
    if (i >= coin_values.size())
        return 0;

    if (target < 0)
        return 0;
    if (target == 0)
        return 1;

    if (dp[i][target] == -1)
    {
        dp[i][target] = (
            solve(i, target - coin_values[i], coin_values, dp) % result_modulo
                + solve(i + 1, target, coin_values, dp) % result_modulo)
            % result_modulo;
    }

    return dp[i][target];
}

As mentioned in the opening post comments, you don’t necessarily need to do the modulo repeatedly, so:

int solve(
    std::vector<long>::size_type i,
    long target,
    std::vector<long> const& coin_values,
    std::vector<std::vector<int>> const& dp)
{
    if (i >= coin_values.size())
        return 0;

    if (target < 0)
        return 0;
    if (target == 0)
        return 1;

    if (dp[i][target] == -1)
    {
        dp[i][target] = (
            solve(i, target - coin_values[i], coin_values, dp)
                + solve(i + 1, target, coin_values, dp))
            % result_modulo;
    }

    return dp[i][target];
}

That’s about all that can be done for solve() for now, let’s move on to main().

    int n,target;
    cin>>n>>target;
    arr.resize(n);
    dp.resize(n+1,vector<int>(target+1,-1));

Alright, the first 3 lines are alright (but, of course, you need better names, and more whitespace, and some comments). In particular, there’s no avoiding allocating space for arr, because you need to read all the coin values, and you need to keep them for the whole algorithm.

Buuuut… what the hell is dp about?

Your allocating a vector of vectors… which almost always a terrible idea, but particularly bad here because n and target are not small. n ranges from 1 to 100—not too bad—while target ranges from 1 to… a million. So in the worst case, that last line allocates 101 vectors of 1,000,000 ints. If an int 4 bytes, as is common, then you are allocating over 4 megabytes of just −1… 101 times. Why? Is that really necessary? Did you think it through?

Note also that it means in the worst case you are allocating over 400 megabytes… when you only have 512 megabytes max. Your problem might not be running out of time, it might be running out of memory.

But even if it isn’t running out of memory, allocating a million ints over a hundred times… yeah, that’s gonna eat up a lot of time. That, along with your design that apparently has solve() called over and over even when the solution has been previously calculated (maybe!), easily explains your time-limit woes.

There’s really nothing more that can be done to improve the code as-is. The problem here is really the design. So, it’s time for a design review.

Design review

It’s very rare that I can say this, but I honestly have not slightest freaking clue what this code is supposed to be doing.

That’s not a good thing.

Yes, part of the problem is that the code is written so unintelligibly, and because it has not even a single comment explaining the logic. But even without those I can usually suss out what code is doing. (I shouldn’t have to; you shouldn’t abuse your code reviewers like that.) In this case, though? No, it just makes no sense.

Let me try and reason through it using the given example, so n is 3, target is 9, and the coins are 2, 3, and 5.

So at, the end of the first run through solve(), solve() is called recursively twice, once with i = 0 and target = 7, and once with i = 1 and target = 9. Let’s dig into these calls, ignoring the memoization for now:

1. i = 0 and target = 7
   1. i = 0 and target = 5
      1. i = 0 and target = 3
         1. i = 0 and target = 1
            1. i = 0 and target = -1 → 0
            2. i = 1 and target = 1
               1. i = 1 and target = -2 → 0
               2. i = 2 and target = 1
                  1. i = 2 and target = -4 → 0
                  2. i = 3 and target = 1 → 0
         2. i = 1 and target = 3
            1. i = 1 and target = 0 → +1 (2+2+2+3)
            2. i = 2 and target = 3
               1. i = 2 and target = -2 → 0
               2. i = 3 and target = 3 → 0
      2. i = 1 and target = 5
         1. i = 1 and target = 2
            1. i = 1 and target = -1 → 0
            2. i = 2 and target = 2
               1. i = 2 and target = -1 → 0
               2. i = 3 and target = 2 → 0
         2. i = 2 and target = 5
            1. i = 2 and target = 0 → +1 (2+2+5)
            2. i = 3 and target = 5 → 0
   2. i = 1 and target = 7
      1. i = 1 and target = 4
         1. i = 1 and target = 1 → 0
            1. i = 1 and target = -2 → 0
            2. i = 2 and target = 1 2. i = 2 and target = -4 → 0 2. i = 3 and target = 1 → 0
         2. i = 2 and target = 4
            1. i = 2 and target = -1 → 0
            2. i = 3 and target = 4 → 0
      2. i = 2 and target = 7
         1. i = 2 and target = 2
            1. i = 2 and target = -3 → 0
            2. i = 3 and target = 2 → 0
         2. i = 3 and target = 7 → 0
2. i = 1 and target = 9
   1. i = 1 and target = 6
      1. i = 1 and target = 3
         1. i = 1 and target = 0 → +1 (3+3+3)
         2. i = 2 and target = 3
            1. i = 2 and target = -2 → 0
            2. i = 3 and target = 3 → 0
      2. i = 2 and target = 6
         1. i = 2 and target = 1
            1. i = 2 and target = -4 → 0
            2. i = 3 and target = 1 → 0
         2. i = 3 and target = 6 → 0
   2. i = 2 and target = 9
      1. i = 2 and target = 4
         1. i = 2 and target = -1 → 0
         2. i = 3 and target = 4 → 0
      2. i = 3 and target = 9 → 0

So it looks like it works: you can see the three expected results there in the chain of computations.

Okay, let’s add the memoization, and see how much it helps:

1. i = 0 and target = 7
   1. i = 0 and target = 5
      1. i = 0 and target = 3
         1. i = 0 and target = 1
            1. i = 0 and target = -1 → 0
            2. i = 1 and target = 1
               1. i = 1 and target = -2 → 0
               2. i = 2 and target = 1
                  1. i = 2 and target = -4 → 0
                  2. i = 3 and target = 1 → 0
         2. i = 1 and target = 3
            1. i = 1 and target = 0 → +1 (2+2+2+3)
            2. i = 2 and target = 3
               1. i = 2 and target = -2 → 0
               2. i = 3 and target = 3 → 0
      2. i = 1 and target = 5
         1. i = 1 and target = 2
            1. i = 1 and target = -1 → 0
            2. i = 2 and target = 2
               1. i = 2 and target = -1 → 0
               2. i = 3 and target = 2 → 0
         2. i = 2 and target = 5
            1. i = 2 and target = 0 → +1 (2+2+5)
            2. i = 3 and target = 5 → 0
   2. i = 1 and target = 7
      1. i = 1 and target = 4
         1. i = 1 and target = 1 → 0
            1. i = 1 and target = -2 → 0
            2. i = 2 and target = 1 → 0 (CACHED!)
         2. i = 2 and target = 4
            1. i = 2 and target = -1 → 0
            2. i = 3 and target = 4 → 0
      2. i = 2 and target = 7
         1. i = 2 and target = 2 → 0 (CACHED!)
         2. i = 3 and target = 7 → 0
2. i = 1 and target = 9
   1. i = 1 and target = 6
      1. i = 1 and target = 3 → +1 (CACHED! (3+3+3))
      2. i = 2 and target = 6
         1. i = 2 and target = 1 → 0 (CACHED!)
         2. i = 3 and target = 6 → 0
   2. i = 2 and target = 9
      1. i = 2 and target = 4 → 0 (CACHED!)
      2. i = 3 and target = 9 → 0

Not really all that much. Granted, this is a small case, but still. Given the incredible costs of your memoization scheme, it’s clearly not worth it.

The worst part is that there should be no need for memoization at all. The only reason you have to consider recalculating the same scenario is because of the way you are doing the calculations. Look at the outline above: once you have figured out “2+2+2=6” and know the remainder is “3”, you throw that information away. Later, on a completely separate path, you discover 6-remainder-3 again, this time via “3+3”. The memoization saves you some extra cycles there, but it shouldn’t be necessary.

I would suggest rethinking the problem. Rather than working your way through the coins from smallest to largest, do the opposite. Go from largest to smallest. The reason is that if you are starting from the smallest coin, then at the top of your recursion you have more possibilities than if you’d started from the largest coin. If you start with 2, then you have to find the coins that sum up to 7… whereas if you start with 5, you only have to find the coins that sum up 4… which will be a much smaller set.

For example:

• Start
  • Current coin: 5; remainder = 4: “5”
    • Current coin: 5; remainder = −1: “5+5” → fail
    • Current coin: 3; remainder = 1: “5+3”
      • Current coin: 3; remainder = −2: “5+3+3” → fail
      • Current coin: 2; remainder = −1: “5+3+2” → fail
    • Current coin: 2; remainder = 2: “5+2”
      • Current coin: 2; remainder = 0: “5+2+2” → success!
  • Current coin: 3; remainder = 6: “3”
    • Current coin: 3; remainder = 3: “3+3”
      • Current coin: 3; remainder = 0: “3+3+3” → success!
      • Current coin: 2; remainder = 1: “3+3+2”
        • Current coin: 2; remainder = −1: “3+3+2+2” → fail
    • Current coin: 2; remainder = 4: “3+2”
      • Current coin: 2; remainder = 2: “3+2+2”
        • Current coin: 2; remainder = 0: “3+2+2+2” → success!
  • Current coin: 2; remainder = 7: “2”
    • Current coin: 2; remainder = 5: “2+2”
      • Current coin: 2; remainder = 3: “2+2+2”
        • Current coin: 2; remainder = 1: “2+2+2+2”
          • Current coin: 2; remainder = −1: “2+2+2+2+2” → fail

See how much smaller it is than the version that goes from smallest coin to largest? Note also that there is no need for memoization, because we don’t consider smaller coins until the last.

(Indeed, a possible optimization is to note when we get to the last coin, we can just do return ((remainder % coin) == 0) ? 1 : 0; (or return not(remainder % coin); if you want to be “clever”). If the remainder is not divisible by the coin value, then it can’t be made up of those coins.)

Another neat feature of doing it this way is that it is easily parallelizable. You could create a sensible number of threads, and then start each top level coin calculation in a different thread.

With these changes, memoization looses its lustre even further. That means those huge allocations become pointless.

Finally, as a matter of principle, you should write better structured code. Your program basically does three things:

1. Read the input parameters (the coins, and the target value).
2. Do the calculation.
3. Write the result.

That means your main() function should be something like:

auto main() -> int
{
    auto const [target, coins] = read_input(std::cin);

    auto const result = calculate_combinations(target, coins);

    std::cout << result;
}

If you want to make I/O just a wee bit faster, then:

auto main() -> int
{
    // Speed up I/O slightly.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    auto const [target, coins] = read_input(std::cin);

    auto const result = calculate_combinations(target, coins);

    std::cout << result;
}

Note the comment explaining the reasoning behind those statements.

The read_input() function is basically just:

auto read_input(std::istream& in)
{
    auto n = 0;     // number of coins
    auto x = 0L;    // target value

    std::cin >> n >> x;
    // note: no error checking, but that's the norm for challenge code

    auto coins = std::vector<long>(n);
    std::ranges::for_each(coins, [](auto& c) { std::cin >> c; });

    return std::tuple{x, std::move(coins)};
}

But!

Here’s the most important thing about writing code properly like this… now you can test read_input() to make sure it’s working. For example:

BOOST_AUTO_TEST_CASE(read_input_example_input)
{
    auto const input = std::istringstream{"3 9\n2 3 5\n"};

    auto const expected_target = 9L;
    auto const expected_coins = std::vector<long>{2, 3, 5};

    auto const [target, coins] = read_input(input);

    BOOST_TEST(target == expected_target);
    BOOST_TEST(coins == expected_coins, boost::test_tools::per_element());
}

And of course, the same reasoning applies to calculate_combinations(). Note that calculate_combinations() does not itself need to be recursive. If you need the current coin index, for example (what you call i), then you’d use a helper function do the actual recursion:

auto calculate_combinations_impl(long target, std::vector<long> const& coins, std::vector<long>::const_reverse_iterator i)
{
    // actual calculation and recursion goes here
}

auto calculate_combinations(long target, std::vector<long> const& coins)
{
    return calculate_combinations_impl(target, coins, coins.rbegin());
}

In summary:

1. Write more legible code. Use whitespace. Use meaningful identifiers.
2. Comment your code!!!
3. Reduce the amount of repeated calculation necessary by reversing the problem: go from largest to smallest coin.
4. Avoid ridiculously large allocations… and especially multiple ridiculously large allocations. If you need a massive allocation, do it all at once. (This is why a vector of vectors is such a stupid idea. Just allocate a single vector, and reduce multidimensional indices to a single dimension (as C arrays do anyway).)