How to find the 4 number sum given an array with no duplicate values and a target sum?

Question

I am trying to find four number sum for a given array. The task is to find all quadruplets in the array that sum up to the target sum and return a two-dimensional array of all these quadruplets in no particular order. If no four unique numbers sum up to the target sum, the function should return an empty array.

I tried following code seems to work fine but I get one additional quadruple because of duplicate element.

  function fourSum([1,2,3,4,5,6,7],10) {
    var hash = {};
    var quadruples = [];
    for(var i=0; i<array.length; i++){
        for(var j=0; j<array.length;j++){
            var Q = 0;
            var P = 0;
            if(i<j){
                Q = array[i]+array[j];

          if(hash[(targetSum - Q)]){
                    for(var k=0; k< hash[(targetSum - Q)].length; k++){
                        var combination = [hash[(targetSum - Q)][k][0] , hash[(targetSum - Q)][k][1] ,array[i], array[j]];
                        quadruples.push(combination);
                    }
                }
            }
            if(i>j){
                P = array[i]+array[j];
                if(hash[P]){
                    hash[P].push([array[i], array[j]]);
                }else{
                    hash[P] = [[array[i], array[j]]];
                }
            }
        }
    }

    return quadruples;
  }

This returns me following: {[2, 1, 2, 5], [2, 1, 3, 4]} which is incorrect because in [2, 1, 2, 5], we have 2 two time. I am unable to find out where I am wrong in my code.

Nina Scholz · Accepted Answer · 2020-02-27T10:50:41.097

I suggest to use a recursive approach and visit all indices only once but store either the element or not and call the funtion again.

This approach has two parts, on function for preparing the result set and make an initial call of the recursive function iter. Tha call starts with index zero, an empty temporary array for collecting items and zero as accumulates sum of the temp array.

The function iter has two parts,

for exit conditions, like
- check if temp has the wanted length, then check total with the wanted sum and take temp as part result. Exit the function/recursion.
- check if total is greater then the sum (this is a short circuit if all numbers are positive) or if index is is not value, then exit the function/recursion.
for calling the iter again
- with new values, like add item and value to total,
- without new values, just increment the index.

function subSetSum(array, sum, length) {
    function iter(index, temp, total) {
        if (temp.length === length) {
            if (total === sum) result.push(temp);
            return;
        }
        if (total > sum || index >= array.length) return;
        iter(index + 1, [...temp, array[index]], total + array[index]);
        iter(index + 1, temp, total);
    }

    var result = []
    iter(0, [], 0);
    return result;
}

console.log(subSetSum([1, 2, 3, 4, 5, 6, 7], 10, 4)); // only a single array
console.log(subSetSum([1, 2, 3, 4, 5, 6, 7], 15, 4));

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

score 0 · Answer 2 · answered Feb 27 '20 at 11:34

We can divide this task into 2 actions:

We could find all combinations of a given array
Find first combination which satisfy condition

So the first action can be done using recursive approach. This code is based on this great answer:

let allCombinations = [];
const getAllCombinations = (set, k, partial) => {
    if (!partial) partial = [];
    for (var element in set) {
        if (k > 1) {
            var set_copy = set.slice();
            set_copy.splice(element, 1);
            getAllCombinations(set_copy, k - 1, partial.concat([set[element]]));
        }
        else {
            allCombinations.push(partial.concat([set[element]]));
        }
    }
}

The second action is to find array which satisfy desired condition:

const findCombination = (arr, desiredSum) => {
    const sum = arr.reduce((a, c) => {
        a+=c;
        return a;
    }, 0);

    if (sum == desiredSum)
        return arr;

    return false;
}

An example:

const getSubsetSum = (arr, sum, length) => {

    let allCombinations = [];
    const getAllCombinations = (set, k, partial) => {
        if (!partial) partial = [];
        for (var element in set) {
            if (k > 1) {
                var set_copy = set.slice();
                set_copy.splice(element, 1);
                getAllCombinations(set_copy, k - 1, partial.concat([set[element]]));
            }
            else {
                allCombinations.push(partial.concat([set[element]]));
            }
        }
    }

    getAllCombinations(arr, length);

    const findCombination = (arr, desiredSum) => {
        const sum = arr.reduce((a, c) => {
            a+=c;
            return a;
        }, 0);

        if (sum == desiredSum)
            return arr;

        return false;
    }

    return allCombinations.find(s => findCombination(s, sum));
}
console.log(getSubsetSum([1, 2, 3, 4, 5, 6, 7], 10, 4));
console.log(getSubsetSum([1, 2, 3, 4, 5, 6, 7], 15, 4));

How to find the 4 number sum given an array with no duplicate values and a target sum?

2 Answers2