Fueled on Bacon

Tag: JavaScript

LeetCode Solutions – Combination Sum II

You can find the original statement of this problem here.

When approaching a problem like this, there’s a few things to notice immediately:

  • Find ALL solutions (usually a backtracking hint)
  • No duplicate solutions (usually means some type of hashing)
  • There’s a target value (defines some type of exit condition)

So right off the bat, I’m going to structure a backtracking solution.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    
    let solution = []
    const backtrack = (rem, sol) => {
      
       if(sum of all elements in sol == target){
          solution.push(sol)
          return
       } 
         
       for(all possibilities){
          
          backtrack()

       }
    }
    backtrack()
    return solution
};

Okay, so that’s my starting point. And from here I need to figure out some details about how to backtrack through this problem.

So the theme of all backtracking is this:

  1. Make a choice
  2. Check to see if you’ve satisfied the condition for success
  3. Unmake that choice
  4. Move on to the next possibility

It is systematic trial and error. In this problem we have a set of candidates that we need to iterate over, they represent our “possibilities” and we need to cover all of them.

Our condition is that the sum of all the elements in an individual solution adds up to the target value. Now that’s going to be a silly operation to add up all the elements of the array every time we want to check for a solution, so we’ll keep a running total.

I’m also going to set my default arguments in this step.

Like so

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    // this is a backtracking problem
    let solution = []
    const backtrack = (rem = candidates, sum = 0,sol = []) => {
       
       if(sum == target){
          solution.push(sol)
          return
       }       
 
       for(let i = 0; i < rem.length; i++){
          let choice = rem[i] 
          
          sum += choice
          
          backtrack(rem, sum, sol)
          
          sum -= choice
       }
    }
    backtrack()
    return solution
};

Notice the sum+ and sum-, that’s the choose/unchoose bit of backtracking at work.

We now need to do our array work. We need to choose/unchoose array elements for our solution. Also notice I’m broadening our termination condition in this step, as not all attempts to find a solution will be successful and we need to prune our results at those points.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    // this is a backtracking problem
    let solution = []
    const backtrack = (rem, sum = 0,sol = []) => {
       if(sum >= target || rem.length == 0){
           if(sum == target){
              solution.push(sol)
           } 
           return
       }
       for(let i = 0; i < rem.length; i++){
          let choice = rem[i] 
          rem.splice(i, 1)
          sum += choice

          sol.push(choice)

          backtrack(rem, sum, sol)
          rem.splice(i,0, choice)

          sol.pop()

          sum -= choice
       }
    }
    backtrack(candidates)
    return solution
};

At this point we have what looks like it could be an intermediate solution to our problem, but it’s not done. In fact, it doesn’t work yet. The above will go through our process, but you’ll end up with an array of empty arrays. Because you’re essentially pushing many references to “sol” onto a solutions array. To get what we want, we need to copy that array. ALSO, we need to eliminate any duplicates, which brings us to the hashing part of the problem.

Whenever you think “eliminate duplicates”, you need to also think “make a hash map and design a good key”.

In our case, that’s going to mean copying our solution array, sorting it, and then stringifying it to make a key. This will make sure that we never end up with duplicates. It will also mean changing our solution variable into an object instead of an array.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    // this is a backtracking problem
    let solution = {}
    const backtrack = (rem, sum = 0,sol = []) => {
       if(sum >= target || rem.length == 0){
           if(sum == target){
              let arr = sol.slice()
              arr.sort((a,b)=>a-b)
              const key = JSON.stringify(arr)
              solution[key] = arr
           } 
           return
       }
       for(let i = 0; i < rem.length; i++){
          let choice = rem[i] 
          rem.splice(i, 1)
          sum += choice
          sol.push(choice)
          backtrack(rem, sum, sol)
          rem.splice(i,0, choice)
          sol.pop()
          sum -= choice
       }
    }
    backtrack(candidates)
    return Object.values(solution)
};

And there you go. This solves the problem.

It’s not a very efficient solution to the problem, but it is a practical solution that any software engineer should be able to see intuitively.

These types of array operations and optimization problems aren’t just for education either. Being well versed in this type of data manipulation comes in handy when building actual software for yourself and for clients.

Related Articles:

FILTER ARTICLES

DATE
TAGS
MORE FROM FOB

Let's get started

Just let us know the basics and we'll send you a Slack invite to discuss with the whole team.

What are we going to be talking about?