请问如何将list中元素划分为两部分，使得这两部分和相同（如果存在这样的划分）？

Question

假设list中有n个元素，如何将该list划分为两部分list1，list2，使之sum(list1) == sum(list2)，如果存在这样的划分的话，否则return -1.（这里的划分是挑选的意思）

Answer 1

背包问题，先加一遍获得sum(all), 然后背包限值为sum(all)/2, 使用动态规划算法或者搜索算法即可解决。

Answer 2

总感觉好像哪里还有问题，但是试了好多组数据，结果又都是正确的，

function sumArray(arr){
  var length = arr.length
  var sum = 0
  for(var i = 0;i<length;i++){
    sum += arr[i] 
  }
  
  return sum
}

function blanceArray(left,right){
  console.log('==========================')
  console.log(left,right)
  var leftsum = sumArray(left)
  var rightsum = sumArray(right)
  console.table(leftsum,rightsum)
  if(leftsum>rightsum){
    return false
  }
  if(leftsum === rightsum){
    return [left,right]
  } else {
    var findnum = (rightsum-leftsum)/2
    for(var i = 0;i<=right.length;i++){
      if(right[i]===findnum){
        left.push(...right.splice(i,1))
        return [left,right]
      }
    }
    left.push(right.pop())
    return blanceArray(left,right)
  }
  
}

function main(arr){
  var sum = sumArray(arr)
  console.log(sum)
  if(sum % 2 !== 0){
    return false
  }
  
  arr.sort(function(a,b){
    return a<b
  })
  
  
  
  var left = [arr.shift()]
  //console.log(arr)
  return blanceArray(left,arr)
  
}

//var testarr = [2,5,6,7,8,4]
var testarr = [3,2,4,3]
var testarr = [1,3,3,6,7,8,16,2]

var result = main(testarr)

console.log(result)

http://jsbin.com/yipuxajala/1...