educative.io

Subset Sum solved with Caterpillar Method, not DP array

Courses
, ,
#1

Contiguous subarray problems can be solved with the Caterpillar Method (2 pointers and a rolling sum). An array of DP calculations is unneeded.

const canPartition = function(arr, s) {
  if(!arr.length) return s === 0;
  if(arr.length === 1) return s === arr[0];
  let head = 0;
  let tail = 0;
  let curr = arr[0];
  // caterpillar method, codility https://bit.ly/2Ol1SXr aka inchworm.
  // It works for contiguous subarray problems without a DP array.
  while(tail < arr.length && head < arr.length) {
    if(curr === s) return true;
    if(arr[head] === s) return true;
    if(arr[head] > s) {
      head++;   // crawl past a rock (element > target)
      tail = head;
      curr = arr[head];
      continue;
    }
    if(curr > s) {
      curr -= arr[tail];
      tail++; // tail retracts
      continue;
    }
    head++;   // head crawls forward
    curr += arr[head];
  }

  return false;
};

console.log(`Can partitioning be done: ---> ${canPartition([1, 2, 3, 4], 6)}`);
console.log(`Can partitioning be done: ---> ${canPartition([1, 2, 7, 1, 5], 10)}`);
console.log(`Can partitioning be done: ---> ${canPartition([1, 3, 4, 8], 6)}`);