How should I implement recursion method to find number of ways to form max heap in C++?

Question

If dp[n] stores the number of ways of forming max heap containing n elements, then we have.

dp[n] = nCr(n - 1, n1) * dp[n1] * dp[n2];

i.e.

1. Select n1 elements out of n - 1 for left subtree.

2. Elements in left subtree can form max heap in dp[n1] ways.

3. Elements in right subtree can form max heap in dp[n2] ways.

How to calculate n1 and n2?

Answer 1

I believe that you're missing the loop that encloses the formula you posted. You vary n1 from 1 through n-1. If "max heap" requires that you consume all n nodes, then you have simply n2 = n-n1. If you can use fewer, then you need another loop to vary n2 from 1 through n-n1.

Return the sum of all those computed quantities.