Complete Insightful Explanation | Recursive and Iterative Solutions
Ignore the provided numbers array for a minute and just consider this:\nIf you wanted to use a numbering system that allowed you to make ANY sum, which numbers 
####  Ignore the provided numbers array for a minute and just consider this:\nIf you wanted to use a numbering system that allowed you to make ANY sum, which numbers would you use?\nWe could just use a sequence of ones [1,1,1,1,..,1], but we would need a LOT of them to make big sums (N of them to make all sums up to N).\n\nWe already know a numbering system that does this well: **binary**.\nWIth each binary digit we have, the largest sum, x, we can make increases by 2x + 1.\nFor example, if we have 4 digits, the largest sum we can make in binary is 2^n - 1 = 15 and it looks like: 1111.\nThe more significant the position, the more the digit is worth:\n* The 0th is worth 2^0 = 1\n* The 1st is worth 2^1 = 2\n* The 2nd is worth 2^2 = 4\n* ..And so on.\n\nIf we showed their values in base 10 in an array, it would look like this: [1, 2, 4, 8, 16, 32, ..., 2^n]\nIn fact, it is this array that is the smallest amount of numbers needed to make any sum!\nIf you understand binary, it should be intuitive why.\n\n#### How can we use this to find a solution?\nIf we want to increase the range of sums we can make, the best we can do is to add double the previous number.\nAnything larger would mean there is a sum that can\'t be made.\nFor example, if we had [1,2,4,9], we could make 7, but not 8, because 9 is larger than 4 * 2.\n\nHowever, we **can** use a number smaller than the previous, it just won\'t increase our range as much.\nWe are interested in minimizing the number of \'patches\' we make, and the numbers provided in the \'nums\' array come for free!\nWe can take advantage of this.\n\n#### OK - Let\'s see a full solution.\n\nWe will keep track of the largest possible sum we can make starting with 0 and incrementally extend it all the way to the target N.\nAt each step, we have two choices:\n* We can use a \'patch\' operation, in which case we would add the value "previous + 1". (Because this is largest we can extend the sum)\n* We can use the number provided in the nums array, which only extends it by the num\'s value, but it comes for free.\n\nAny time we CAN use the number provided, we should! This greedy approach yields an optimal solution.\nBut when CAN\'T we use the provided number? When it\'s **larger** than previous + 1!\n\nThat brings us full circle to a solution we can implement.\nI hope this was useful!\n\n#### Below are iterative and recursive implementations (in JS) for the described solution:\n\n**Recursive:**\n```js\n/**\n* @param tgt - The target sum.\n* @param cnt - Counts the number of patch operations so far.\n* @param S - Tracks the largest sum we can currently reach.\n* @param nums - The array of provided numbers\n*/\nlet solve = (tgt, cnt, S, [head, ...tail]) => {\n    // Base Case -> We can now reach the target sum\n    if (S >= tgt) return cnt\n    \n    // We\'re out of provided numbers -> Patch the largest reachable num (previous + 1).\n    if (!head) return solve(tgt, cnt + 1, S + S + 1, [])\n    \n    // We CAN reach the next number -> Extend the range by that amount.\n    if (head <= S + 1) return solve(tgt, cnt, S + head, tail)\n\n    // Can\'t reach the next number -> Patch the largest reachable num.\n    return solve(tgt, cnt + 1, S + S + 1, [head, ...tail])\n}\n\nlet minPatches = (nums, n) => solve(n, 0, 0, nums)\n```\n\n**Iterative:**\n```js\nvar minPatches = function(nums, n) {\n    // Counts the number of patch operations.\n    let operations = 0\n    \n    // Tracks the index in the nums array we are at. Moves left to right.\n    let idx = 0\n    \n    // Tracks highest sum we can make using numbers below \'idx\' and with \'operations\'.\n    let upper = 0\n    \n    // Keeping going until we can reach the target sum, n.\n    while (upper < n) {\n        \n        if (idx < nums.length && nums[idx] <= upper + 1) {\n            // If we can reach the next num, use it and extend the range (upper) by that amount.\n            upper += nums[idx++]\n        } else {\n            // We can\'t reach the next num, so we need to patch.\n            // For the patch, we want to extend the range as far as possible.\n            // That is, upper + 1\n            operations += 1\n            upper += upper + 1\n        }\n    }\n    return operations\n};\n```
[]