Skip to main content
Practice

Explanation for Adding 1, 2, 3

The challenge is to find all possible combinations of a given number n as a sum of 1, 2, and 3.

This function employs the dynamic programming technique using the tabulation method.

Tabulation involves storing computed results in a table, allowing reuse of these values in further calculations.


Function Implementation​

  1. Handle Base Cases:

    • When n < 3, return n as it is. For n being 1 or 2, the possible combinations are 1 and 2 respectively.

    • If n == 3, the number of combinations is 4, hence return 4.

  2. Initialize Array for Tabulation:

    • The dp array is initialized as [0, 1, 2, 4]. Here, dp[i] will store the number of combinations for n=i.

  3. Calculate Number of Combinations Using Dynamic Programming:

    • For each number from 4 to n, update dp[i] by summing dp[i - 1], dp[i - 2], and dp[i - 3]. This implies that the number of ways to reach n=i is the sum of ways to reach n=i-1, n=i-2, and n=i-3.

Model Solution
def solution(n):
    # Handle base cases
    if n < 3:
        return n
    if n == 3:
        return 4

    # Initialize array for tabulation
    dp = [0, 1, 2, 4]

    # Calculate number of combinations using dynamic programming
    for i in range(4, n + 1):
        dp.append(dp[i - 1] + dp[i - 2] + dp[i - 3])

    return dp[n]

Usage Example​

Input/Output Example
print(solution(4))  # Output: 7

When calling solution(4), the number of combinations to form 4 are:

  1. 1 + 1 + 1 + 1
  2. 1 + 1 + 2
  3. 1 + 2 + 1
  4. 2 + 1 + 1
  5. 2 + 2
  6. 1 + 3
  7. 3 + 1

Thus, there are 7 such ways, correctly confirmed by the function returning 7.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.