Когда вам нужно подсчитать возможности получения суммы, вы должны рассмотреть возможности, когда вы не используете определенную монету, а где вы делаете ее (при не реже одного раза). Когда вы знаете количество возможностей для первого случая и для второго случая, тогда вы знаете ответ: это сумма этих двух.
Итак, теперь возникает вопрос, как я могу посчитать количество возможностей в этих двух разных случаях?
В первом случае вы упрощаете задачу, поскольку исключаете тип монеты, уменьшая количество различных типов монет, из которых вы все еще можете выбирать.
Во втором случае вы уменьшаете оставшуюся сумму для покрытия, так как вы взяли монету. Это также уменьшает проблему: не с точки зрения доступных монет, а с точки зрения суммирования.
В любом случае вы можете применить тот же алгоритм к сокращенной задаче. Вот где возникает рекурсия: эти уменьшенные проблемы снова разделятся на случай, когда вы используете монету или нет, ... et c.
В конце концов проблема будет настолько уменьшена, что вы легко сможете знать количество возможных для этого:
Если оставшаяся сумма равна нулю: это именно то, к чему мы стремились: рассматривать выбор монет, который привел к этому моменту, как допустимую возможность, и верните 1.
если оставшаяся сумма отрицательна, значит, вы, по-видимому, использовали слишком большую монету, и вы не должны считать это действительным: верните 0 как количество возможностей.
Если оставшаяся сумма строго положительна, и монет не осталось: очевидно, мы выбросили последний оставшийся вид монеты. Это не хорошо. Мы не можем считать это возможным, поэтому верните 0
Эти значения (0 или 1) всплывут вверх по дереву рекурсии, где вы их сложите. Эта сумма, в свою очередь, также вернется дальше вверх по дереву рекурсии, пока, в конце концов, не будут сложены все возможности.