Problem Link

Difficulty: Medium

2023-10-15-13-43-50.png

Go ahead and read the problem statement

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 deciding when to stop and hence optimizing the solution.

[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.

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]

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.

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
        );
      }
    }
  }
}