每日算法：N數(shù)之和

請用算法實現(xiàn)，從給定的無需、不重復的數(shù)組A中，取出N個數(shù)，使其相加和為M。并給出算法的時間、空間復雜度，如：

var arr = [1, 4, 7, 11, 9, 8, 10, 6];
var N = 3;
var M = 27;

Result:
[7, 11, 9], [11, 10, 6], [9, 8, 10]

解題思路：利用二進制

根據(jù)數(shù)組長度構建二進制數(shù)據(jù)，再選擇其中滿足條件的數(shù)據(jù)。

我們用 1 和 0 來表示數(shù)組中某位元素是否被選中。因此，可以用 0110 來表示數(shù)組中第 1 位和第 2 位被選中了。

所以，本題可以解讀為：

• 數(shù)組中被選中的個數(shù)是 N 。
• 被選中的和是 M 。

我們的算法思路逐漸清晰起來：遍歷所有二進制，判斷選中個數(shù)是否為 N ，然后再求對應的元素之和，看其是否為 M 。

1. 從數(shù)組中取出 N 個數(shù)

例如：

var arr = [1, 2, 3, 4];
var N = 3;
var M = 6;

如何判斷 N=3 是，對應的選取二進制中有幾個 1 喃？

最簡單的方式就是：

const n = num => num.toString(2).replace(/0/g, '').length

這里我們嘗試使用一下位運算來解決本題，因為位運算是不需要編譯的（位運算直接用二進制進行表示，省去了中間過程的各種復雜轉換，提高了速度），肯定速度最快。

我們知道 1&0=0 、 1&1=1 ，1111&1110=1110 ，即 15&14=14 ，所以我們每次 & 比自身小 1 的數(shù)都會消除一個 1 ，所以這里建立一個迭代，通過統(tǒng)計消除的次數(shù)，就能確定最終有幾個 1 了：

const n = num => {
  let count = 0
  while(num) {
    num &= (num - 1)
    count++
  }
  return count
}

2. 和為 M

現(xiàn)在最后一層判斷就是選取的這些數(shù)字和必須等于 M ，即根據(jù) N 生成的對應二進制所在元素上的和 是否為 M

比如 1110 ，我們應該判斷 arr[0] + arr[1] + arr[2] 是否為 M。

那么問題也就轉化成了如何判斷數(shù)組下標是否在 1110 中呢？如何在則求和

其實也很簡單，比如下標 1 在，而下標 3 不在。我們把 1 轉化成 0100 ， 1110 & 0100  為 1100, 大于 0 ，因此下標 1 在。而 1110 & 0001 為 0 ，因此 下標 3 不在。

所以求和我們可以如下實現(xiàn)：

let arr = [1,2,3,4]
// i 為滿足條件的二進制
let i = 0b1110
let s = 0, temp = []
let len = arr.length
for (let j = 0; j < len; j++) {
  if ( i & 1 << (len - 1 - j)) {
 s += arr[j]
 temp.push(arr[j])
  }
}
console.log(temp)
// => [1, 2, 3]

最終實現(xiàn)

// 參數(shù)依次為目標數(shù)組、選取元素數(shù)目、目標和
const search = (arr, count, sum) => {
  // 計算某選擇情況下有幾個 1，也就是選擇元素的個數(shù)
  const getCount = num => {
    let count = 0
    while(num) {
      num &= (num - 1)
      count++
    }
    return count
  }

  let len = arr.length, bit = 1 << len, res = []
  
  // 遍歷所有的選擇情況
  for(let i = 1; i < bit; i++){
    // 滿足選擇的元素個數(shù) === count
    if(getCount(i) === count){
      let s = 0, temp = []

      // 每一種滿足個數(shù)為 N 的選擇情況下，繼續(xù)判斷是否滿足 和為 M
      for(let j = 0; j < len; j++){
        // 建立映射，找出選擇位上的元素
        if(i & 1 << (len - 1 -j)) {
          s += arr[j]
          temp.push(arr[j])
        }
      }

      // 如果這種選擇情況滿足和為 M
      if(s === sum) {
        res.push(temp)
      }
    }
  }

  return res
}