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.

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.

Copy
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]

Copy
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.