字节：N数之和

请用算法实现，从给定的无需、不重复的数组A中，取出N个数，使其相加和为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]

function numSum(nums, n, m) {
  if (!nums.length || nums.length < n) return [];
  nums = nums.sort((a, b) => a - b);
  const result = [];
  const stack = [];

  const backtrace = (start) => {
    if (stack.length === n - 1) {
      let end = nums.length - 1;

      while (start <= end) {
        const temp = stack.reduce((acc, cur) => acc + cur);
        if (temp + nums[start] === m) {
          result.push([...stack, nums[start]]);
        }
        if (start !== end && temp + nums[end] === m) {
          result.push([...stack, nums[end]]);
        }
        start++;
        end--;
      }
      return;
    }

    for (let i = start; i < nums.length; i++) {
      stack.push(nums[i]);
      backtrace(i + 1);
      stack.pop();
    }
  };
  backtrace(0);
  return result;
}

解题思路：利用二进制

根据数组长度构建二进制数据，再选择其中满足条件的数据。

我们用 1 和 0 来表示数组中某位元素是否被选中。因此，可以用 0110 来表示数组中第 1 位和第 2 位被选中了。

所以，本题可以解读为：

数组中被选中的个数是 N 。
被选中的和是 M 。

我们的算法思路逐渐清晰起来：遍历所有二进制，判断选中个数是否为 N ，然后再求对应的元素之和，看其是否为 M 。

1. 从数组中取出 N 个数

例如：

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 的数都会消除一个 1 ，所以这里建立一个迭代，通过统计消除的次数，就能确定最终有几个 1 了：

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

2. 和为 M

现在最后一层判断就是选取的这些数字和必须等于 M ，即根据 N 生成的对应二进制所在元素上的和是否为 M

比如 1110 ，我们应该判断 arr[0] + arr[1] + arr[2] 是否为 M。

那么问题也就转化成了如何判断数组下标是否在 1110 中呢？如何在则求和

其实也很简单，比如下标 1 在，而下标 3 不在。我们把 1 转化成 0100 ， 1110 & 0100 为 0100, 大于 0 ，因此下标 1 在。而 1110 & 0001 为 0 ，因此下标 3 不在。

所以求和我们可以如下实现：

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]

最终实现

// 参数依次为目标数组、选取元素数目、目标和
const search = (arr, count, sum) => {
  // 计算某选择情况下有几个 1，也就是选择元素的个数
  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++){
    // 满足选择的元素个数 === count
    if(getCount(i) === count){
      let s = 0, temp = []

      // 每一种满足个数为 N 的选择情况下，继续判断是否满足 和为 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
}

回溯的时间复杂度一般是O(n*n!)

https://leetcode-cn.com/circle/article/a8L9ER/ 参考下这个 n 数

/**
 * 1. 可以使用指针等方法实现 之前在看代码随想录的时候已经实现过
 * let arr = [1,4,7,11,9,8,10,6]
 * let N = 3;
 * let M = 27
 */
function findSum(arr, count, sum) {
    const getCount = function (n) {
        let count = 0;
        while (n) {
            n &= (n - 1)
            count++
        }
        return count
    }
    let len = arr.length, bit = 1 << len
    console.log('bit: ', parseInt(bit).toString(2));//bit:  1 0000 0000
    let res = []
    for (let i = 1; i < bit; i++) {
        if (getCount(i) === count) {
            let s = 0, temp = []
            for (let j = 0; j < len; j++) {
                //判断下标i是否在对应的二进制位置上
                if (i & 1 << (len-1-j)) {
                    s += arr[j]
                    temp.push(arr[j])
                }
            }
            if (s === sum) {
                res.push(temp)
            }
        }
    }
    return res
}
let arr = [1, 4, 7, 11,9,8,10,6]
let N = 2;
let M = 5
console.log(findSum(arr, N, M))
let num = 1<<7
console.log(parseInt(num).toString(2))//10000000

function numSum(nums, n, m, arr = [], ans = [], index = 0) {
  if(arr.length === n) return arr.reduce((a,b) => a + b, 0) === m && ans.push([...arr])
  for(let i=index; i<nums.length; i++){
    arr.push(nums[i])
    numSum(nums, n, m, arr, ans, i + 1)
    arr.pop()
  }
  return ans
}

function numSum(nums, n, m) {
    if (!nums.length || !n || !m) return [];
    let res = [], path = [], currentSum = 0;
    let backtrace = (index) => {
        if (path.length == n) {
            if (currentSum === m) {
                res.push([...path]);  // 创建path的一个副本
            }
            return;
        }
        for (let i = index; i < nums.length; i++) {
            path.push(nums[i]);
            currentSum += nums[i];  // 更新当前路径和
            backtrace(i + 1);
            currentSum -= nums[i];  // 回溯时，恢复路径和
            path.pop();
        }
    }
    backtrace(0);
    return res;
}

Navigation Menu

Repository navigation

字节：N数之和 #128

解题思路：利用二进制

1. 从数组中取出 N 个数

2. 和为 M

最终实现

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

字节：N数之和 #128

Description

Activity

JerryWen1994 commented on Nov 16, 2020

sisterAn commented on Nov 16, 2020

解题思路：利用二进制

1. 从数组中取出 N 个数

2. 和为 M

最终实现

maimang511 commented on Dec 20, 2020

webLiang commented on Sep 26, 2021

xllpiupiu commented on Oct 5, 2021

NoBey commented on Mar 23, 2022

black-posterus commented on Apr 26, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions