How to find number of ways that the integers 1,2,3 can add up to n?

Question

Given a set of integers 1,2, and 3, find the number of ways that these can add up to n. (The order matters, i.e. say n is 5. 1+2+1+1 and 2+1+1+1 are two distinct solutions)

My solution involves splitting n into a list of 1s so if n = 5, A = [1,1,1,1,1]. And I will generate more sublists recursively from each list by adding adjacent numbers. So A will generate 4 more lists: [2,1,1,1], [1,2,1,1], [1,1,2,1],[1,1,1,2], and each of these lists will generate further sublists until it reaches a terminating case like [3,2] or [2,3]

Here is my proposed solution (in Python)

ways = []
def check_terminating(A,n):
    # check for terminating case
    for i in range(len(A)-1):
        if A[i] + A[i+1] <= 3:
            return False # means still can compute
    return True

def count_ways(n,A=[]):
    if A in ways:
       # check if alr computed if yes then don't compute
       return True
    if A not in ways: # check for duplicates
        ways.append(A) # global ways
    if check_terminating(A,n):
        return True # end of the tree
    for i in range(len(A)-1):
        # for each index i,
        # combine with the next element and form a new list
        total = A[i] + A[i+1]
        print(total)
        if total <= 3:
            # form new list and compute
            newA = A[:i] + [total] + A[i+2:]
            count_ways(A,newA)
            # recursive call

# main            
n = 5
A = [1 for _ in range(n)]

count_ways(5,A)
print("No. of ways for n = {} is {}".format(n,len(ways)))

May I know if I'm on the right track, and if so, is there any way to make this code more efficient?

Please note that this is not a coin change problem. In coin change, order of occurrence is not important. In my problem, 1+2+1+1 is different from 1+1+1+2 but in coin change, both are same. Please don't post coin change solutions for this answer.

Edit: My code is working but I would like to know if there are better solutions. Thank you for all your help :)

Answer 1

The recurrence relation is F(n+3)=F(n+2)+F(n+1)+F(n) with F(0)=1, F(-1)=F(-2)=0. These are the tribonacci numbers (a variant of the Fibonacci numbers):

It's possible to write an easy O(n) solution:

def count_ways(n):
    a, b, c = 1, 0, 0
    for _ in xrange(n):
        a, b, c = a+b+c, a, b
    return a

It's harder, but possible to compute the result in relatively few arithmetic operations:

def count_ways(n):
    A = 3**(n+3)
    P = A**3-A**2-A-1
    return pow(A, n+3, P) % A

for i in xrange(20):
    print i, count_ways(i)

Answer 2

The idea that you describe sounds right. It is easy to write a recursive function that produces the correct answer..slowly.

You can then make it faster by memoizing the answer. Just keep a dictionary of answers that you've already calculated. In your recursive function look at whether you have a precalculated answer. If so, return it. If not, calculate it, save that answer in the dictionary, then return the answer.

That version should run quickly.

Answer 3

An O(n) method is possible:

def countways(n):
    A=[1,1,2]
    while len(A)<=n:
        A.append(A[-1]+A[-2]+A[-3])
    return A[n]

The idea is that we can work out how many ways of making a sequence with n by considering each choice (1,2,3) for the last partition size.

e.g. to count choices for (1,1,1,1) consider:

1. choices for (1,1,1) followed by a 1
2. choices for (1,1) followed by a 2
3. choices for (1) followed by a 3

If you need the results (instead of just the count) you can adapt this approach as follows:

cache = {}
def countwaysb(n):
    if n < 0:
        return []
    if n == 0:
        return [[]]
    if n in cache:
        return cache[n]
    A = []
    for last in range(1,4):
        for B in countwaysb(n-last):
            A.append(B+[last])
    cache[n] = A   
    return A