Facebook | Phone screen | Split array equal sum
Francisco Becker
1292
Jul 17, 2020
Jul 17, 2020
BacktrackingJavaScript

This is what I was able to come up with for the Facebook question:

You're given an array made up of positive integers. Split the given array into two smaller arrays where the sums of each smaller array are equal. Print out the two smaller arrays.

-> had to ask for clarification: print any arbitary error message if the given array isn't splitable.

eg.
[1,2,1,1,3] -> [1,2,1] & [1,3]
[1,1,1,1,1,5] -> [1,1,1,1,1] & [5]
[5,2,3] -> [5] & [2,3]

This is a screenshot from the output of the code below: [1,2,3,4,5,6,7]
image

/**
Needs a little refactoring but it gets the job done.
 */
var canPartition = function(nums) {
  nums.sort((a,b)=>a-b);
  let sum = 0;
  for(let i = 0; i < nums.length; i++){
    sum += nums[i];
  }
  if(sum % 2 !== 0) return false;
  const half = sum/2;
  const res = [];
  btk(nums, [], 0, half, 0, res)
  return res.length >= 2
};

function btk(nums, arr, total, half, index, res, vals =[]){
  if(total == half){
    const otherHalf = getOtherHalf(arr, half, nums )
    if(otherHalf){
      res.push(vals.concat(), otherHalf)
    }
    return res
  }
  
  for(let i = index; i < nums.length; i++){
    total += nums[i];
    arr.push(i);//push index
    vals.push(nums[i])
    btk(nums, arr, total, half, i+1, res, vals)
    arr.pop()
    total -= vals.pop();
  }
  return res;
}
  
function getOtherHalf(found, half, nums){
  const otherHalf = [];
  let sum = 0;
  for(let i = 0; i < nums.length; i++){
    if(found.indexOf(i) !== -1) continue;    
    sum += nums[i];
    otherHalf.push(nums[i])
  }  
  if(sum == half){
    return otherHalf;
  }
  return null;
}
Comments (1)