Skip to content

Score Combinations in Football

Level: L3-L4 Topics: Dynamic Programming, Combinatorics, Permutations vs Combinations

Problem Statement

In American football, points can be scored in the following ways:

  • Touchdown (TD): 6 points
  • Field Goal (FG): 3 points
  • Safety: 2 points
  • Extra Point: 1 point (can only occur after a touchdown)
  • Two-Point Conversion: 2 points (can only occur after a touchdown)

After each touchdown, the team gets exactly one attempt at either an extra point (1) or a two-point conversion (2). So a touchdown effectively scores 7 (TD + extra point) or 8 (TD + two-point conversion) or 6 (if the extra point/conversion fails, but for simplicity assume one of 6, 7, or 8).

Given a final score, list all possible scoring sequences (ordered sequences of scoring events) that produce that score.

Background & Constraints

  • The scoring values to consider are: 2 (safety), 3 (field goal), 6 (TD, failed conversion), 7 (TD + extra point), 8 (TD + two-point conversion).
  • Order matters: TD then FG is different from FG then TD. This makes the problem about permutations, not combinations.
  • The final score is a positive integer, typically up to 100 or so.
  • You need to enumerate all distinct ordered sequences of scoring events.

Examples

Example 1:

Final score: 6

Possible sequences:
1. [6]                    (one touchdown, failed conversion)
2. [3, 3]                (two field goals)
3. [2, 2, 2]             (three safeties)
4. [2, 4-wait, no 4]
Let me list properly:
1. [6]
2. [3, 3]
3. [2, 2, 2]

But wait, the problem is about ordered sequences:
Since [3, 3] is the same scoring event twice, there's only one such sequence.

For score 6: {[6], [3,3], [2,2,2]}
Total: 3 sequences (if we only use 2, 3, 6 as our base scoring events)

Example 2:

Final score: 9

Some possible sequences using {2, 3, 6, 7, 8}:
- [7, 2] — TD + extra point, then safety
- [2, 7] — safety, then TD + extra point
- [3, 6] — FG, then TD (failed conversion)
- [6, 3] — TD (failed conversion), then FG
- [3, 3, 3] — three field goals
- [2, 2, 2, 3] — three safeties + FG (multiple orderings)
- [2, 3, 2, 2], [3, 2, 2, 2], [2, 2, 3, 2] — other orderings
... and so on.

Hints & Common Pitfalls

  • This is permutation-based, not combination-based. Unlike the classic coin change "number of ways" problem (which counts combinations), here the order of scoring events matters. [3, 2] and [2, 3] are different sequences.
  • DP approach: Let dp[s] = number of ordered sequences that sum to score s. For each score value v in {2, 3, 6, 7, 8}: dp[s] += dp[s - v]. Base case: dp[0] = 1.
  • Key difference from coin change: In standard coin change combinations, you iterate coins in an outer loop and sums in an inner loop to avoid counting order. Here, you iterate sums in the outer loop and scoring values in the inner loop, which counts all orderings.
  • To enumerate all sequences (not just count them), use recursion/backtracking with memoization for counting.
  • Common mistake: Treating this as a combination problem and missing permutations.
  • Common mistake: Forgetting that extra points and two-point conversions can only follow touchdowns. If the problem requires strict NFL rules, you need to pair post-TD events with touchdowns (resulting in composite scores of 6, 7, or 8).

Follow-Up Questions

  1. What is the time and space complexity of counting all ordered sequences?
  2. How would you modify the solution to count combinations instead (order doesn't matter)?
  3. Can you solve this with a linear DP approach and explain why it works?
  4. Generalize the solution for an arbitrary set of scoring values. How does the number of sequences grow?
  5. What if you also need to track which specific scoring events occurred (e.g., distinguish "TD + extra" from "TD + 2pt")? How does this change the enumeration?