Рекурсивная функция в C для поиска арифметических комбинаций для любого числа N

Question

Я нахожусь в процессе обучения C. Мой вопрос следующий: дана серия из числа

1 * + 2 * + 3 * + 5 .... * + 9

или

Где число n может быть создано любой комбинацией любой из цифр от 1 до 9 путем добавления, умножения или обоих, например:

1 + 2 + 3 + 4 * 5 * 6 * 7 * 8 * 9 = 60486

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

Очевидно, существует набор чисел, которые могут быть представлены с помощью различных комбинаций вышеуказанного. Моя рекурсивная функция должна возвращать, сколько разных уникальных представлений число N имеет в вышеуказанном формате.

До сих пор я работал над решением, подобным этому:

int recCheckSolutions(int n, int idx, int tree[], int cnt, int sum)
{
    if (n == sum)
        return 1;
    if (idx > 9)
        return 0;
    if (sum >= n)
        return 0;
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum += idx);
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum *= idx);
    return cnt;
}

Функция вызывается так:

int solutions = recCheckSolutions(n, 0, tree, 0, 0);

где n желаемое число, для которого мы хотим найти комбинации сумма является целочисленной переменной, используемой, чтобы увидеть, где мы находимся в наших расчетах а tree [] - это реализация дерева, которое я использовал, чтобы проверить, какие числа были вычислены (очевидно, более не актуальны в этой реализации, но все еще могут быть полезны?)

Это имеет некоторое правильное поведение, я выполнил трассировку / отладку стека, и, похоже, у него есть какое-то решение, однако оно не заканчивается правильным результатом. Вполне возможно, что я лаю не на том дереве.

Большое спасибо за ваши отзывы и помощь.

Answer 1

Вы правильно поняли большинство вещей, кроме условий возврата:

int recCheckSolutions(int n, int idx, int tree[], int cnt, int sum)
{
    if (idx == 9)
        return 1;
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum += idx);
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum *= idx);
    return cnt;
}