Backtracking Solution JavaScript with explanation


  • 0
    K
    var combine = function(n, k) {
        const result = []
        
        function findCombinations(subArr, start) {
          // basecase. If our subArray is the length of k, we push a copy of the array into result
          if(subArr.length === k) {
            result.push(arr.slice())
          }
          
          // We need all the numbers from 1..n, so we must loop from 1..n to get all values
          for(let i = start; i <= n; i++) {
            // for each iteration, we push into subArray the starting value to build the array
            subArr.push(i)
            
           // immediately recurse increasing the starting value of i by 1. We need this to build the subArr 
          // from [] -> [1] -> [1, 2]. The next value of i will allow the next value to be pushed into the subArr
            findCombinations(arr, i+1)
    
          // We remove the last value we added to clean subArr for the next new starting number.
         // If we built all the values with 1, [1,2], [1,3], [1,4], we now pop 1 off and 
        // begin the loop with 2. [2, 3], [2, 4] 
           subArr.pop()
          }
        }
        
       // start subArray with an empty array that we will populate. The problem states we need numbers 
      // from 1..n, so we start counting at 1
        findCombinations([], 1)
        return result
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.