Combination Sum II — Interesting Recursion Problem

Photo by Szabo Viktor on Unsplash

I was asked this problem in an interview and found it very interesting. I gave a solution that was not as optimal as final solution.

Recursive problems are usually intuitive and easy to implement. But the optimal solution of this problem requires additional effort and it taught me something and that’s why I decided to post this.

Problem Link

Difficulty: Medium

Below is the problem statement in brief.

Given an array of positive integers (say candidates) and another number target, possibly with duplicates, we need to find all possible sets of numbers that sum up to a given target number.

Example:

Candidates: [10,1,2,7,6,1,5]
Target: 8
Answer:
[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6],
]

A basic solution would be to have all possible combinations. But that would not be optimal and also give duplicate sets.

Sorting this array would help us in building the sum incrementally and deciding when to stop and hence optimizing the solution. We will see that sorting will also help us in avoiding duplicates.

[10,1,2,7,6,1,5] // original array
[1,1,2,5,6,7,10] // after sorting

Now we can traverse through the array and decide whether or not to use a number in forming the sum.

Based on the selected number we can have different set of numbers from the rest of the array for the remaining sum.
This gives us the idea of solving sub-problems, and thus we will go for a recursive solution (top-down approach).

Let’s do a dry run before we get to coding.

target: 8,
numbers to use: [1,1,2,5,6,7,10]

We can decide to use 1

remaining target: 7
remaining numbers to use [1,2,5,6,7,10]

At each stage of recursion, we loop through the numbers to use each number, and reduce the overall sum, and recusively call the function to select next numbers.

Take a look at this diagram to understand how we get a solution.

Dry run of the approach

We will store the used numbers in an array usedValues, and once the target reduces to 0 we will add that to the solution set and end the recursion.

Also if we choose a set of numbers where the required sum can’t be achieved, we will end the recursion.

It is important to realise that in each stage of recusion, we are choosing only one number.

var combinationSum2 = function (candidates, target) {
  let solutionSets = [];
  candidates = candidates.sort((a, b) => a - b);
  recursiveCheck(candidates, 0, target, [], solutionSets);
  return solutionSets;
};

function recursiveCheck(
  candidates,
  position,
  target,
  usedValues,
  solutionSets
) {
  for (let i = position; i < candidates.length; i++) {
    let num = candidates[i];
    if (num > target) {
      return;
    } else {
      let newTarget = target - num;
      let newUsedValues = [...usedValues, num];
      if (newTarget == 0) {
        solutionSets.push(newUsedValues);
        return;
      } else {
        recursiveCheck(
          candidates,
          i + 1,
          newTarget,
          newUsedValues,
          solutionSets
        );
      }
    }
  }
}

You will find that the current solution does not prevent duplicate sets. We will see the following set of numbers appearing twice because we chose 1 at the same level again.

[1,2,5]
[1,2,5]

Duplicate solutions

Now the interesting part of the problem:

How to avoid duplicates

Duplicates will always happen as the same number in same order:

1, 2, 5
1, 2, 5

To avoid duplicates, we can make sure that at each stage of recursion, we don’t want to choose the same number again, i.e., in the for loop, if we reach the same number as the previously selected one we can prevent recursing with that number again.

How to avoid duplicates

We can guarantee that only one element from duplicates be selected at each level of recursion with the help from the fact that the array is sorted.

So the final solution will be something like this.

function recursiveCheck(
  candidates,
  position,
  target,
  usedValues,
  solutionSets
) {
  let pre = -1;

  for (let i = position; i < candidates.length; i++) {
    let num = candidates[i];
    if (num > target) {
      return;
    } else {
      if (num == pre) {
        continue;
      }
      pre = num;
      let newTarget = target - num;
      let newUsedValues = [...usedValues, num];
      if (newTarget == 0) {
        solutionSets.add(newUsedValues);
        return;
      } else {
        recursiveCheck(
          candidates,
          i + 1,
          newTarget,
          newUsedValues,
          solutionSets
        );
      }
    }
  }
}

Lastly, here is my blog where I post most of my blogs as well.