Power set size

Challenge

Implement:

long long power_set_size(int n);

Return the number of subsets of an n-element set (2^n), computed recursively. 0 <= n <= 62.

Input format

n in [0,62].

Output format

2^n.

Constraints

Use long long.

Starter code

#include <stddef.h>
/* Size of the power set of an n-element set = 2^n, computed recursively. 0<=n<=62. */
long long power_set_size(int n){ (void)n; return 0; }

Common mistakes

Wrong base case (2^0 is 1, not 0).

Edge cases to handle

The empty set has exactly 1 subset (itself).

Background lessons

• Divide and conquer