find sum of element that is equal to key value-CodePudding

here is a given array with elements, there is key also. you have to find all possible elements whose sum is equal to the key.

the answer should be [12,5,3],[7,3,10],[3,4,2,6] time complexity with in n2

let array = [12, 5, 7, 3, 4, 10, 2, 6]; let key = 20;

const arr = [12, 5, 7, 3, 4, 10, 2, 6];
let key = 20;
let i = 0;
let j = i   1;
const elem = [];

for (let i = 0; i < arr.length; i  ) {
  let j = i   1;
  let sum = arr[i];
  elem.push(arr[i]);
  while (j < arr.length) {
    sum  = arr[j];
    elem.push(arr[j]);
    if (sum == key) {
      console.log("here it is", elem);
    } else if (sum > key) {
      elem.pop();
      sum -= arr[j];
    }
    j  ;
  }
  elem.splice(0, elem.length);
  sum = 0;
}

CodePudding user response：

This is quite lengthy but it does give one approach one can take; it does give the idea of a recursive function would not be difficult to come up with.

const input = [12, 5, 7, 3, 4, 10, 2, 6],
      key = 20,
      
               //Combine elements in twos
      output = input.reduce(
          (prev,cur,i,arr) => 
          [
              ...prev, 
              ...arr.filter((v,j) => i !== j)
                  .map(v => [cur, v])
                  .filter(([a,b]) => a   b <= key)
          ], []
      )
      //if any twos add up to key, keep otherwise add a third different element
      .reduce(
          (prev,[a,b]) => 
          a   b === key ? [...prev, [a,b]] :
          [
              ...prev,
              ...input.filter(v => ![a,b].includes(v))
                  .map(v => [a,b,v])
                  .filter(([a,b,c]) => a   b   c <= key)
          ], []
      )
      //if any threes add up to key, keep otherwise add a fourth different element
      // and keep only fours that add up to key
      .reduce(
          (prev,[a,b,c]) =>
          a   b   c === key ? [...prev, [a,b,c]] :
          [
              ...prev,
              ...input.filter(v => ![a,b,c].includes(v))
                  .map(v => [a,b,c,v])
                  .filter(([a,b,c,d]) => a   b   c   d === key)
          ], []
      )
      //remove "duplicates"
      .reduce(
          (prev,cur) =>
          prev.find(a => a.every(e => cur.includes(e))) ? 
          prev :
          [...prev,cur], []
      );
      
console.log( output );

NOTE

This does not exhaust all the possible answers. For instance [3,4,2,6,5] is a possible answer so an additional step of fives is needed. So you would continue to add an element until all new elements as long as there's at least a group that add up to below key. Recursion would handle this quite well.

CodePudding user response：

This is a variant of the subsetSum problem. Usually the question is phrased in terms of finding out if any subset sums to the target number. Finding them all is likely to be a more time-consuming problem; I don't know if there is an o(n²) solution for that. Here's a simple recursive version that might get you started:

const subsetSum = (t, [n, ...ns]) =>
  n == undefined 
    ? t == 0 ? [[]] : []
    : [... subsetSum (t - n, ns) .map (s => [n, ...s]), ... subsetSum (t, ns)] 

console .log (subsetSum (20, [12, 5, 7, 3, 4, 10, 2, 6]))

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

Here if the array is empty, we return a single empty array if the target is zero, and no results if its not. Otherwise, we recur twice: Once using the first number (and prepending it to any result) and the other without it, combining all the results into a single array.

This version will handle negative and positive numbers. If you can guarantee they're all positive, there might be additional optimizations.

If there is a more optimal solution, it probably involves dynamic programming, and you might want to look there.