Can't find algorithm for specific rules

December 22, 2022

I’m trying to implement in rust an algorithm that given a number generate
an array containing every combinations possible obeying to those rules:

A number in the combination is always equal or less than the previous one
No number greater than 4 are accepted
A combinations ends when the sum of the number containing it is equal the given number

For the example, given the number 3, we will get the following array:

[    
    [3],
    [2, 1],
    [1, 1, 1],
]

And given the number 6:

[    
    [4, 2],
    [4, 1, 1],
    [3, 3],
    [3, 2, 1],
    [3, 1, 1, 1],
    [2, 2, 2],
    [2, 2, 1, 1],
    [2, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1],
]

I’m trying to develop this in rust, but since i’m quite new to the language and do not have an algorithm to rely upon i need some help. Whether pseudo code or code without GC will be fine.

>Solution :

I think the below code does what you want.

res = []


def generate_combinations(num, current_combination):
    # base case
    if num < 0:
        return
    if num == 0:
        res.append(current_combination.copy())
        return
    # recursion
    if current_combination:
        end = current_combination[-1]
    else:
        end = 4
    for i in range(end, 0, -1):
        current_combination.append(i)
        generate_combinations(num - i, current_combination)
        current_combination.pop()