Recursion to find n numbers in a range that add up to a target value

Question

I've written a function that finds all sets of two numbers that sum a target value, given a range of numbers from 0 to x. I'm trying to rewrite it in a way so that you can get a result of a given length n (not only 2), but n numbers that will equal a target when added together.

For example, if the range is 1 to 5 and you want to find all sets of three numbers that add up to 7, the answer would be:

[[1,1,5], [1,2,4], [1,3,3], [2,2,3]]

It looks like the solution is to use a recursive function, but I can't quite figure out how to do this. I've looked at several subset-sum examples on StackOverflow, but none seem to match this particular scenario.

This is not a homework problem. Any help would be appreciated. Here is my findPairs function:

function findPairs(arr, target) {
    var pairs = [];
    var first = 0;
    var last = arr.length-1;
    while (first <= last) {
      var sum = arr[first] + arr[last];
      if (sum === target) {
        pairs.push([arr[first], arr[last]]);
        first ++;
        last--;
      }
      else if (sum < target) {
        first++;
      }
      else {
        last--;
      }
    }
    return pairs;
  }

  var sample = _.range(11);
  console.log(JSON.stringify(findPairs(sample,12)));
  // Returns
  // [[2,10],[3,9],[4,8],[5,7],[6,6]]

This example uses the lodash _.range function. Fiddle here: https://jsfiddle.net/tbarmann/muoms1vL/10/

Answer 1

You could indeed use recursion. Define the third argument as the length of the sub-arrays you are looking for, and define a recursion function inside that function as follows:

function findSums(arr, target, count) {
    var result = [];
    function recurse(start, leftOver, selection) {
        if (leftOver < 0) return; // failure
        if (leftOver === 0 && selection.length == count) {
            result.push(selection); // add solution
            return;
        }
        for (var i = start; i < arr.length; i++) {
            recurse(i, leftOver-arr[i], selection.concat(arr[i]));
        }
    }
    recurse(0, target, []);
    return result;
}
// Demo
var result = findSums([1,2,3,4,5], 7, 3);
console.log(result);   

.as-console-wrapper { max-height: 100% !important; top: 0; }

Remarks

The solution does not require that the input array has consecutive numbers (range): you might pass it [3,6,4,2,1]. The sub-arrays that are returned will keep the selected elements in order, for example: [3,3,3], [3,4,2] and [6,2,1] could be solutions for targetting 9 with 3 values for that example input.

The numbers must all be non-negative. If negative values are to be allowed, then the optimisation if (leftOver < 0) return; must be removed from the code.

Answer 2

function sumPermutations(target, range, number) {
  var result = [];

  function combo(left, group, sum) {
    if(sum > target) return null;
    if (left == 0) {
      if(sum == target) return group;
      return null;
    }
    
    for (var i = range.min; i <= range.max; i++) {
       var r = combo(left - 1, group.concat(i), sum + i);
      if (r)
        result.push(r);
    }
  }
  combo(number, [], 0);

  return result;
}

console.log(sumPermutations(7, {min: 1, max: 5}, 3));

Note: This gives results with duplicates (all permutaions including those with different orders). You can remove duplicates by sorting the arrays and join thier items and hash them into a hash object.

Answer 3

Well, what you are probably looking for is Dynamic Programming. It is an approach where you define mathematically your problem and a recursive solution. Then you try to find a solution, using memoization.

I would make a helper function, where the arguments are (range, target, lengthOfResult). Then do something like:

func helper(arr, target, lengthOfResult){
    if(taget == 0) continue;
    for(int i=1; i<arr.length-1; i++){
        if(taget - arr[i] < 0) return [];
        var sub_results = helper(arr, taget - arr[i], lengthOfResult - 1)
        foreach(var res in sub_results){
            result.concat([arr[i]] + res);
        }
    }
    return result;
}

So you are changing the question for the helper function to "Give me all lists of length-1 which sums up to taget-arr[i]", append to that arr[i]. Then use that to construct the result, for each arr[i].

---

Basically, every iteration the length will decrease, so the function will terminate at some point. You subtract from the taget whatever number you have now. So you're end result will add up to the desired target.

• Note that this algorithm works only with positive numbers. If you can allow negatives, you should remove the if inside the first for-loop.
• About the memoization, if you want to allow using each number only once, you could get away with a single array. If you allow reoccurring numbers in the result (like in your example), you probably need a grid; horizontally the target, vertically the lengthOfResult. Then in the beginning of each invocation of the helper method, you check if you already calculated that value. This will save you some recursive calls and make the algorithm not exponential.