Count compositions

Challenge

Implement:

long long count_compositions(int n);

Return the number of ordered ways to write n as a sum of positive integers (compositions). count(0)=1. 0 <= n <= 62.

Input format

n in [0,62].

Output format

Number of compositions (2^(n-1) for n>=1).

Constraints

Memoize the recursion.

Starter code

#include <stddef.h>
/* Number of ordered ways to write n as a sum of positive integers (compositions). count(0)=1. 0<=n<=62. */
long long count_compositions(int n){ (void)n; return 0; }

Common mistakes

Exponential recursion without memoization; miscounting the empty case.

Edge cases to handle

0 has 1 composition (the empty sum).

Background lessons

• Counting with recursion