Skip to content

Instantly share code, notes, and snippets.

@sebinsua
Last active Nov 19, 2020
Embed
What would you like to do?
const defaultKey = (arr) => arr.join("");
function createPermute(toKey = defaultKey) {
return function* permute(arr, length = arr.length) {
if (length > arr.length) {
throw new Error(
`The permutation size required (${length}) is greater than the size of the array supplied (${arr.length}).`
);
}
if (arr.length === 0) {
return;
}
if (arr.length === 1) {
yield [arr[0]];
return;
}
if (arr.length === 2) {
const [a, b] = arr;
yield [a, b];
yield [b, a];
return;
}
let seen = new Set();
for (let idx = 0; idx < arr.length; idx++) {
const first = arr[idx];
const tail = [...arr];
tail.splice(idx, 1);
for (let part of permute(tail, length - 1)) {
const permutation = [first, ...part].slice(0, length);
const key = toKey(permutation);
if (seen.has(key)) {
continue;
}
seen.add(key);
yield permutation;
}
}
};
}
function kSum(k) {
const combinations = createPermute((arr) =>
[...arr].sort((a, b) => a - b).join("")
);
const sum = (values) => values.reduce((a, b) => a + b, 0);
return function* (arr, target = 0) {
for (let values of combinations(arr, k)) {
if (sum(values) === target) {
yield values;
}
}
};
}
const threeSum = kSum(3);
const fourSum = kSum(4);
console.log("threeSum", Array.from(threeSum([-1, 0, 1])));
console.log("fourSum", Array.from(fourSum([-1, -1, 1, 1, 0, 0, -2, 2, -4, 6])));
@sebinsua
Copy link
Author

sebinsua commented Nov 16, 2020

This first version was based on my original permutations/combinations code.

See: https://codesandbox.io/s/elastic-montalcini-q6s5j?file=/src/index.js:0-1326

I realise this is likely very inefficient and that the recursion is dangerous due to stack overflows however it's a working solution. I'll go back to the drawing board for the next version...!

@sebinsua
Copy link
Author

sebinsua commented Nov 19, 2020

function* threeSum(_nums, target = 0) {
  const nums = [..._nums].sort((a, b) => a - b);

  for (let adx = 0; adx < nums.length - 2; adx++) {
    const a = nums[adx];

    let bdx = adx + 1;
    let cdx = nums.length - 1;
    while (bdx < cdx) {
      const b = nums[bdx];
      const c = nums[cdx];

      const sum = a + b + c;

      if (sum === target) {
        yield [a, b, c];

        while (bdx < cdx && b === nums[bdx + 1]) bdx++;
        while (bdx < cdx && c === nums[cdx - 1]) cdx--;

        bdx++;
        cdx--;
      } else if (sum < target) {
        bdx++;
      } /* if (sum > target) */ else {
        cdx--;
      }
    }

    while (a === nums[adx + 1]) adx++;
  }
}

for (let values of threeSum([-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4])) {
  console.log("threeSum", values);
}

See: https://codesandbox.io/s/patient-dream-2hiwx?file=/src/index.js:0-799

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment