How to find all combinations of certain terms of a number?

Question

Algorithms

It is necessary to bypass the combinations of all the terms of the number (the order is important), the terms are predetermined, for example, 1.12 and 24. I.e. if the number is 48, then it can be: 12,12,12,12 or 24,24 or 24,1,11,1,1,1,1,1... Etc.

Answer 1

There are a lot of different combinations. So, since you bypass them all, the exhaustive search will not work much slower. It can then be optimized.
Write a recursive function that receives 2 parameters as input: how much is left to get, what is the maximum term that can be used. The current terms either go as the third parameter or are generally stored in a global variable.
The function iterates over 2 options. Let the remaining sum be s, and the allowed maximum number be i (they are stored in some kind of sorted a[]).
1) We take the current maximum term. Naturally, if it is placed in the remainder of s >= a[i]. We put it to the current terms in the array and recursively call from the reduced remainder, without changing the maximum number -(s-a[i], i). Important - if the terms are stored in a global variable, then after the recursive call "return as it was" - remove the newly added term from the array.
2) Skip the current maximum number. So, you can't take it anymore. Calling from (s, i-1). Naturally, this option is only available if i>0.
If we get that the remaining sum sis equal to zero, then we have chosen a partition, we need to derive the current terms.
Oh yes, for this method to work well, it makes sense to sort the terms in ascending order. So that the largest ones are taken first.
If there is no 1 among the possible terms, then this exhaustive search can lead to dead ends. For example, the terms 6 and 11 are available, you need to dial 29. The algorithm can skip 11 and try to dial 29 with sixes alone, but this will never work. These extra dead-end branches can be cut and thus speed up the solution in some cases.
For this, see the knapsack problem . Almost like in it, do dynamic programming, which will count how many ways to collect a given sum of k small terms. After that, in the recursive function, you can immediately return if the DP says that the options to type s with the first i terms are 0.
In addition, if you only need the number of options, and not the partitions themselves, then you do not need enumeration, but only dynamic programming.
EDIT: I just noticed that the order is important for you and 1,2,3 is considered separately from 3,1,2
The changes are simple - the recursive function now takes only one parameter - how much is left to get. Instead of two options, it sorts out N options - which number of those allowed to take.
The optimization is the same. implement a DP that counts how many ways to collect a given number and, if there are no ways, we return from the function.

Answer 2

1. From the smallest of the given (1) - find the target (48=1+1+...+1).
2. Remove the first terms (12 * 1) and move on to the next IN ORDER! (12), adding it at the end, removing all unnecessary (1) at the beginning. Again we find the target (48=1+...+1+12, 48=1+1+..+12+12, ...)
3. And so on. we do for all given numbers, gradually replacing the terms IN THE ORDER OF THEIR SEQUENCE and NOT SKIP ("the chain" should not be broken)! (48=1+...+1+12+24)
It is not necessary to enumerate permutations here, because the order of the terms is strictly fixed.