Combination sum problem

Learn how to solve the combination sum problem in javascript.

Given an array of integers and target we have to find all the sub-arrays whose sum is equal to that target.

Example

Input:
arr = [2, 3, 5];
target = 8;

Output:
[
  [2, 2, 2, 2],
  [2, 3, 3],
  [3, 5]
]

We are going to see two different solutions for this.
1. Only unique combinations possible.
2. Duplicate combinations allowed.

Combination sum problem to find only unique combinations.

We are going to use the backtracking technique to solve this problem. In backtracking we call the same function recursively with all combinations possible and then store only the desired result.

To get the unique combinations we backtrack after then current index, not from the start.

const combinationSum = (arr, target) => {
  //Track the current sub-array
  let temp = [];
  //Store the fincal result
  let result = [];
  //Track the current sum
  let sum = 0;
  //Track the index
  let index = 0;
  
  const backtrack = (temp, sum, index) => {
    //If current sum is greater than target then terminate the execution
    if(sum > target){
      return;
    }
    
    //If current sum is equal to the target then store the sub-array
    if(sum === target){
      result.push([...temp]);
      return;
    }
    
    //Backtrack all the possible combinations after the current index to get only unique combinations
    for(let i = index; i < arr.length; i++){
      temp.push(arr[i]);
      backtrack(temp, sum + arr[i], i);
      temp.pop();
    }
  }
  
  //Initiate the backtracking
  backtrack(temp, sum, index);
  
  //Return the result
  return result;
}

Input:
const arr = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(arr, target));

Output:
[[2, 2, 3], [7]]

Time complexity: O(n ^ 2).
Space complexity: O(n ^ 2) (considering the call stack).

---

To find the duplicate combinations.

In order to find the duplicate combinations we use the above method, but rather than starting the backtracking from the current index, we do it from the start to get all possible combinations.

const combinationSum = (arr, target) => {
  //Track the current sub-array
  let temp = [];
  //Store the fincal result
  let result = [];
  //Track the current sum
  let sum = 0;
  //Track the index
  let index = 0;
  
  const backtrack = (temp, sum, index) => {
    //If current sum is greater than target then terminate the execution
    if(sum > target){
      return;
    }
    
    //If current sum is equal to the target then store the sub-array
    if(sum === target){
      result.push([...temp]);
      return;
    }
    
    //Backtrack all the possible combinations to get only duplicate combinations
    for(let i = 0; i < arr.length; i++){
      temp.push(arr[i]);
      backtrack(temp, sum + arr[i], i);
      temp.pop();
    }
  }
  
  //Initiate the backtracking
  backtrack(temp, sum, index);
  
  //Return the result
  return result;
}

Input:
const arr = [2, 3, 5];
const target = 8;
console.log(combinationSum(arr, target));

Output:
[[2, 2, 2, 2], [2, 3, 3], [3, 2, 3], [3, 3, 2], [3, 5], [5, 3]]

Time complexity: O(n ^ 2).
Space complexity: O(n ^ 2) (considering the call stack).