[JavaScript] Backtracking
This is basically the same as the other "generate permutations" problems with an extra constraint. (By the way, I quite literally learned 99% of my backtracking
This is basically the same as the other "generate permutations" problems with an extra constraint. (By the way, I quite literally learned 99% of my backtracking and "generate permutations" techniques from watching this video series: https://www.youtube.com/watch?v=RkXl5iYoQn4&ab_channel=happygirlzt)\n\nSo anyways, what would be the base case? I knew that we\'d be decrementing N, and that the base case is if the remaining N becomes 0.\n\nIt also occurred to me that we should keep track of what the start index is, so that we don\'t put an "e" before an "a."\n`a -> e -> i -> o -> u`\n\nHere is the first version of code that I wrote. In this case, I modelled it after the other permutation problems and actually generated all the different permutations.\n```js\nvar countVowelStrings = function(n) {    \n    const res = []\n    const curr = []\n    helper(res, curr, n, [\'a\',\'e\',\'i\',\'o\',\'u\'], 0)\n\n    return res.length\n};\n\nfunction helper(res, curr, n, arr, startIdx) { \n    // base case\n    if (n === 0) {\n        res.push([...curr]) // here I am creating a new copy of `curr` and adding it into `res`\n        return\n    }\n\n    // recursive case\n    for (let i = startIdx; i < arr.length; i++) {\n        // choose \n        curr.push(arr[i])\n        helper(res, curr, n - 1, arr, i) // Here, it\'s important to pass in "i" as the new "startIdx," so that we make sure "e" does not go before "a," etc.\n        \n        // unchoose\n        curr.pop()\n    }\n}\n```\n\nThe above code is needlessly memory-intensive. And that is because the question doesn\'t actually require us to generate the actual permutations. So here is the code that I wrote, after removing all the part about actually generating the permutations.\n\n```js\nvar countVowelStrings = function(n) {    \n    let res = 0\n    \n    helper(n, 0)\n\n    function helper(n, startIdx) { \n        // base case\n        if (n === 0) {\n            res++\n            return\n        }\n\n        // recursive case\n        for (let i = startIdx; i < 5; i++) {\n            helper(n - 1, i)\n        }\n    }\n\n    return res\n};\n```\n\nI found the runtime complexity to be tricky to figure out, but I know for sure that it won\'t be over O(5^N) (O(branches^levels)). Space is O(N) because of the stack frames we are generating via recursion.
['JavaScript']