Maximum Points in an Archery Competition - Backtracking [JS]
Description Solution: Backtracking Use backtracking to find all combinations of using the arrows. For each slot, try two choices: Don't use any arrows Use aliceArrows[idx] + 1 arrows to gain idx number of points Note: When we fill all slots and still have some arrows left, we can put the extra arrows in any slot. In this solution, I have placed them in the last slot. Time Complexity: O(2^n) 80ms Space Complexity: O(2^n) 42.7MB var maximumBobPoints = function ( numArrows, aliceArrows ) { let max = 0 , n = aliceArrows.length, res; backtrack(numArrows, 0 , 0 , Array (n).fill( 0 )); return res; function backtrack ( arrows, idx, points, bobArrows ) { if (idx === n || arrows === 0 ) { let origVal = bobArrows[n - 1 ]; if (arrows > 0 ) bobArrows[n - 1 ] += arrows; // put extra arrows in any slot if (points > max) { max = points; res = [...bobArrows]; } bobArrows[n - 1 ] = origVal; return ; ...