[C++] Recursive Vs. Math Solutions Compared and Explained, 100% Time, 100% Space
The core intuition here, came to me by just looking at the second example with n == 2.\n\ncpp\n"aa", "ae", "ai", "ao", "au", // all the combinations of {\'a\', 
The core intuition here, came to me by just looking at the second example with `n == 2`.\n\n```cpp\n"aa", "ae", "ai", "ao", "au", // all the combinations of {\'a\', \'e\', \'i\', \'o\', \'u\'} from the level before with \'a\' prepended\n"ee", "ei", "eo", "eu",       // all the combinations of {\'e\', \'i\', \'o\', \'u\'} from the level before with \'e\' prepended\n"ii", "io", "iu",             // all the combinations of {\'i\', \'o\', \'u\'} from the level before with \'i\' prepended\n"oo", "ou",                   // all the combinations of {\'o\', \'u\'} from the level before with \'o\' prepended\n"uu"                          // all the combinations of {\'u\'} from the level before with \'u\' prepended\n```\n\nIf you consider `n == 3`, it is easier to think that you will get all the elements starting with `\'a\'` by just prepending that character in front of our previous results and so on.\n\nMore in general we will have `5` times all the combinations you can get with `5` elements for `n - 1`, plus `4` times all the combinations you can get with `4` elements and `n -1` and so on.\n\nWhen `n == 1` we can just return `k` (there are only `k` possible permutations of size `1` when you have `k` elements) and that is our base case; we also need to terminate the recursive calls when `k < 1`, since there are no possible combinations and we can add this as another base case, returning `0`.\n\nFinally, we can compose the general case as explained in 2 paragraphs above, as the result of calling `countVowelStrings` `5` times, decreasing `n` by `1` and further reducing `k` at each successive call.\n\nI know I could have used a loop, but I am a sucker for one-liner, so here it is!\n\nThe code, which scores about 5%, time, but almost 100% memory despite all the recursive call stack:\n\n```cpp\nclass Solution {\npublic:\n    int countVowelStrings(int n, int k = 5) {\n        return k < 1 ? 0 : n == 1 ? k : (countVowelStrings(--n, k--) + countVowelStrings(n, k--) + countVowelStrings(n, k--) + countVowelStrings(n, k--) + countVowelStrings(n, k--));\n    }\n};\n```\n\nAnd this is if you could not figure out/remember the math in 30 mins (as I failed to d), otherwise you will just have to bow to the awesomely simplicity of combinatorics and compute the product of all the numbers in the `(n + 1) - (n+ 4)` range and divide it by the `4!`.\n\nIf you want to look a bit deeper at it, just consider that after picking `4` elements in our range, we only have one left and thus our solution can be computed at `n + 4` choose `4` - [formula and explanation](https://en.wikipedia.org/wiki/Binomial_coefficient).\n\nThe 100% Time, 100% Space code:\n\n```cpp\nclass Solution {\npublic:\n    int countVowelStrings(int n, int k = 5) {\n        return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;\n    }\n};\n```
['C', 'Combinatorics', 'Probability and Statistics', 'C++']