20180927

给定一个集合，如 {3, 4, 5, -3, 100, 1, 89, 54, 23, 20},将它分成两个子集，每个是它的一半大小。 如果集合元素是奇数，那么有一个自己会比另一个子集大1。

集合用数组S表示，写一个方法tug(S)，使得S切分成两个子集后，两个子集元素和的差值（绝对值）最小。

比如{3, 4, 5, -3, 100, 1, 89, 54, 23, 20}可以拆分成 {4, 100, 1, 23, 20}和{3, 5, -3, 89, 54}，和分别是148，148,差值为0。

{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}可以拆分成{45, -34, 12, 98, -1}和{23, 0, -99, 4, 189, 4}，和分别是120和121，差值为1。

示例

tug([23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4])
// [ [45 ,-34, 12 ,98 ,-1], [23, 0, -99, 4, 189 ,4] ]

提示：见tips.md

答案：

枚举集合S中的所有子集（可以利用类似全排列）的方法，利用决策树选中所有规模为一半的子集，然后求和。

const sum = (arr) => arr.reduce((a,b) => a + b, 0)
function tug(S) {
  const total = sum(S)
  let min = Infinity
  let list = null
  /* 递归枚举所有的情况 */
  function tug_util(S, decisions = []) {
    if(decisions.length === ~~(S.length / 2)) {
      const s = sum(decisions.map(i => S[i]))
      const t = Math.abs(total - 2*s) // 两个子集和的差值（绝对值）
      if(min > t) {
        min = t
        list = [
          decisions.map(i => S[i]),
          [...Array(S.length)].map((_, i)=>i).filter(i => decisions.indexOf(i) === -1).map(i => S[i])
        ]
      }
      return
    }
    const start = decisions.length > 0 ? decisions[decisions.length - 1] : -1
    for(let i = start + 1; i < S.length; i++) {
      tug_util(S, decisions.concat(i))
    }
  }
  tug_util(S)
  return list
}