Thread: Help with C combinatronics problem

Hi, I'm learning combinatronics and algorithms in C at uni and stumbled upon this problem which I'm struggling to solve. I'm posting here after trying for 3 days to write a decent solution, but the only one that works is basically a recursive brute force, which is less than ideal. I would really appreciate any help, especially with the recursive function.

A jeweler has z sapphires, r rubies, t topazes, and s emeralds to create a necklace by stringing one stone after another.
He must, however, meet the following rules:

- a sapphire must be followed immediately by either another sapphire or a ruby
- an emerald must be followed immediately by either another emerald or a topaz
- a ruby must be followed immediately by either an emerald or a topaz
- a topaz must be followed immediately by either a sapphire or a ruby.

Write a C function that calculates the length and displays the composition of a maximum-length necklace that obeys the above rules. The length of the necklace is the number of gemstones in it.
Remark: the length of the solution can vary between 1 and (z+r+t+s).
Hint: the exercise can be solved by adopting an approach similar to that of arrangements with repetition, if appropriately adopted to the requirements of the problem. Once the recursive model is set up, write the filter function (acceptability check) and the optimization function. We finally evaluate the possibility to introduce criteria of pruning.
Note: Pay attention to the increase of the execution time required to identify the solution as the values of the input parameters for the problem increase (number of available gems).