interview_question

n_sum.js

/* 问题：
 * n-sum subset
 *
 * 在一个集合中，寻找一个由n个元素组成的子集，其和等于target
 *
 */
function randomArray(n) {
  let data = Array(n)
              .fill()
              .map(e=>Math.round(Math.random() * 2 * n))
  // data = [1,2,423,23,43,1234,4,5,6,8,34,123]
  data = Array.from(new Set(data))
  return data
}

function sumAll(data){
  let sum = 0
  for (var i = 0; i < data.length; ++i) {
    sum += data[i]
  }
  return sum
}

function sumFromLeft(data, start, count) {
  let sum = data[start]
  for (var i = 0; i < count; ++i) {
    sum += data[start+i+1]
  }
  return sum
}
function sumFromRight(data, start, count) {
  let sum = data[start]
  let len = data.length
  for (var i = 0; i < count; ++i) {
    sum += data[len-1]
  }
  return sum
}


function finder(data, target, start_idx, n_count, seq, tmp){

  // 当只有一个数的时候，直接查找
  if (n_count == 1) {
    if (data.indexOf(target)) {
      seq.push(target)
      return true
    }
    return false
  }

  // 当有两个数时，从数组两头开始相加
  if (n_count == 2) {
    let left = start_idx
    let right = data.length - 1
    while (left < right) {
      let sum = data[left]+ data[right]
      if (sum == target) {
        for (let t in tmp) {
          seq.push(tmp[t])
        }
        seq.push(data[left])
        seq.push(data[right])
        // break
        return true
      } else if (sum < target ) left++
      else right--
    }
    return false
  }

  // 当有三个以上数时，递归 + 回溯
  for (let i = start_idx; i < data.length-n_count+1; i++) {

    // check and cutting branches to improve speed
    if (sumFromLeft(data, start_idx, n_count-1) > target) return false
    if (sumFromRight(data, start_idx, n_count-1) < target) continue

    tmp.push(data[i])
    let has_res = finder(data, target - data[i], i + 1, n_count - 1, seq, tmp);
    tmp.pop()

    if (has_res) return true
  }

}

function getResult(data, target, n_count) {

  let seq = []

  if (data.length < n_count ) return seq

  data.sort((a,b)=>a-b)

  let tmp = []
  finder(data, target, 0, n_count, seq, tmp)

  console.log("====")
  console.log(seq)
  console.log("Sum:", sumAll(seq))
  return seq
}

let DATA = randomArray(500)

getResult(DATA, 34, 1)
getResult(DATA, 11, 2)
getResult(DATA, 15, 3)
getResult(DATA, 125, 8)
getResult(DATA, 32, 3)
getResult(DATA, 3223, 33)