美文网首页
从一个数组中找出 N 个数,其和为 M 的所有可能

从一个数组中找出 N 个数,其和为 M 的所有可能

作者: 织雪纱奈 | 来源:发表于2019-12-09 17:44 被阅读0次
 // 参数依次为目标数组、选取元素数目、目标和
        const search = (arr, count, sum) => {
          // 计算某选择情况下有几个 `1`,也就是选择元素的个数
          const n = 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(n(i) === count){
                console.log(111 ,i , parseInt(i).toString(2))

              let s = 0, temp = []

              // 每一种满足个数为 N 的选择情况下,继续判断是否满足 和为 M
              for(let j = 0; j < len; j++){
                // 建立映射,找出选择位上的元素
                if((i & 1 << j) !== 0) {
                  s += arr[j]
                  temp.push(arr[j])
                }
              }

              // 如果这种选择情况满足和为 M
              if(s === sum) {
                res.push(temp)
              }
            }
          }

          return res
        }

相关文章

网友评论

      本文标题:从一个数组中找出 N 个数,其和为 M 的所有可能

      本文链接:https://www.haomeiwen.com/subject/ofligctx.html