0

In an American football game, a play can lead to 2 points (safety), 3 points (field goal), or 7 points (touchdown, assuming the extra point). Many different combinations of 2, 3, and 7 point plays can make up a final score.

Write a program that takes a final score and scores for individual plays, and returns the number of combinations of plays that result in the final score.

I was able to come up with solution that has space complexity of O(sn), where n = # of scores, and s= final score.

Now, I'm trying to improve it to use only O(s). It is a straight-forward for permutation, but I have no clue on how to prevent duplicates for combinations with only O(s).

kevinJiang99
  • 81
  • 1
  • It might not be a dupe if all you are interested in is improving your existing solution complexity as you describe in the last sentence, but if this is the case - please explicitly say that and give your solution in the questoin itself. (I will reopen if this is the case). – amit Jan 14 '17 at 17:30
  • Thanks amit. I was able to solve this problem easily in the same way. I should've searched with different keywords before I posted this question. – kevinJiang99 Jan 14 '17 at 17:43

0 Answers0