How should i write a function(n) to calculate all possible sequences that consits of only 1, 3, 4

Question

I have a task to write a function(n) that finds all the sequences that consists of only 1, 3, 4 (not sure how to explain it in english but i have example below)

For example if n is equal to five then i should print out

5 = 1+1+1+1+1
5 = 1+1+3
5 = 1+3+1
5 = 3+1+1
5 = 1+4
5 = 4+1

I'm not sure how should i go about writing it.

Is there a boundary for this problem? For example if n is 1000, you ll get huge results? — Yunus Temurlenk, May 26 '20 at 11:27
i forgot to put a boundary but yes, it was specified. Maximum n is100 — vynnix, May 26 '20 at 11:30
@YunusTemurlenk I think the bound is "all combinations taht add up 5, consisting of only 1, 3 and 4's" — Christopher, May 26 '20 at 11:36
This sounds like a variation of the coin change problem. Take a look here: https://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value — NewPythonUser, May 26 '20 at 11:31

score 0 · Answer 1 · answered May 26 '20 at 11:43

Just finding the right terminology might be an answer:

"You are trying to get all the permutations of the values 1, 3 and 4, that sum up to 5."

Unlike combinations, with permutation the order maters. Wich is why {1,4} and {4,1} are both seperate, valid answers. Same with the {1,1,3} variations. I would say this is a hard recursive problem. I am a bit a a loss for the function signature right now, as the reference nature of arras could become a big issue.

just finding all the combinations and then creating all the permutations of each set could work.

How should i write a function(n) to calculate all possible sequences that consits of only 1, 3, 4

1 Answers1