Combination Sum | Backtracking Algorithm

You are given an array of distinct integers nums and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Example 1:

Input: 
nums = [2,5,6,9] 
target = 9

Output: [[2,2,5],[9]]

Explanation:

2 + 2 + 5 = 9. We use 2 twice, and 5 once.

9 = 9. We use 9 once.

Example 2:

Input: 
nums = [3,4,5]
target = 16

Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]

Example 3:

Input: 
nums = [3]
target = 5

Output: []

function backTrack(start, currentList){
 #sum of currentList
 #sum === target? store the currentList for result

 # if sum is greather than target invalid path, return back
  
 #iterate over each element given
 for(let i = start,  i < nums.length; i++){
   #include current element and explore all paths
   
   #backTrack with  multiple frequence of current element
  
   #exclude current element and explore all paths
 
 }
 
}

const results = [];

function backTrack(start, currentList) {
  let sum = currentList.reduce((acc, curr) => acc + curr, 0);
  if (sum === target) {
    results.push([...currentList]);
  }

  if (target < sum) {
    return;
  }

  for (let i = start; i < nums.length; i++) {
    // include current and explore
    currentList.push(nums[i]);
    
    // include multiple frequence of current element
    backTrack(i, currentList);

    // exclude current and explore
    currentList.pop();
  }
}

backTrack(0, []);
return results;

#backtracking #datastructure #combinationSum #sumTarget