#include <iostream>
#include <cstdlib>

using namespace std;

int countWays(int n); //I think there is a chance this is redundant but I saw it was included in factorial2.C

int main()
{
	int n {1};
	
	cout << "Enter a number to find amount of parenthesizing possibilities ";
	cin >> n;

	if (!cin) {
       		cerr << "Sorry, that is not a whole number.\n";
		return EXIT_FAILURE;
        }

	const int possibilities {countWays(n)};

	cout << "There are " << possibilities << " ways to parenthesize the sum of " << n << " numbers.\n";

	return EXIT_SUCCESS;
}

int countWays(int n)
{
	if (n < 1) {
		cerr << "Number is too low.\n";
		exit(EXIT_FAILURE);
	}

	if (n == 1) {
		return 1;
	}

	int totalWays {0};

	for (int i {1}; i < n; ++i) {
		totalWays += countWays(i) * countWays(n-i);
	}

	return totalWays;
}