【Q673】求给定数组中 N 个数相加之和为 sum 所有可能集合

[shfshanyue]

求给定数组中 N 个数相加之和为 sum 所有可能集合，请补充以下代码

function fn(arr, n, sum) {}

[shfshanyue]

TODO

[heretic-G]

function fun (arr, n, sum) {
    let result = []
    if (arr.length < n) return -1
    arr.sort((prev, next) => {
        return prev - next
    })
    function getSum (arr, n, currSum, index, incArr = []) {
        for (let i = index; i < arr.length; i++) {
            let temp = currSum + arr[i]
            if (temp > sum) break

            if (n > 1) {
                getSum(arr, n - 1, temp, i + 1, [arr[i], ...incArr])
            }

            if (n === 1 && temp === sum) {
                result.push([arr[i], ...incArr]) 
            }
        }
    }
    getSum(arr, n, 0, 0)
    return result
}

[haotie1990]

function findSumNumbers(array, n, sum) {
  // 枚举所有n个数的组合，判断组合的和等于sum
  let result = [];
  const generateAll = function(index, collection, arr) {
    if (collection.length === n) {
      const s = collection.reduce((acc, c) => acc += c, 0);
      if (s === sum) {
        result.push(collection);
      }
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      generateAll(index + 1, collection.concat(arr[i]), arr.slice(i + 1));
    }
  }
  generateAll(0, [], array.slice(0));
  return result;
}

findSumNumbers([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2, 10);

findSumNumbers([1, 0, -1, 0, -2, 2], 4, 0);

[shen076]

https://leetcode.cn/problems/combination-sum-ii/

[JamiLanister]

function fun(arr, n, sum) {
    let ans = []
    let combination = []
    function handle(start, array) {
        ans.push([...array]);
        for (let i=start; i<arr.length; i++) {
            array.push(arr[i])
            handle(i+1, array)
            array.pop()
        }
    }
    handle(0, [])

    function add(list) {
        return list.reduce((prev,cur) => prev+cur, 0)
    }
    for (let key of ans) {
        if (key.length === n && add(key) === sum) {
            combination.push([...key])
        }
    }
    return combination
}

console.log(fun([2,3,6, -1,7,-2,9], 2, 5))

[JLUssh]

利用到两个元素相加为target，然后在此基础上使用变成三个元素、四个元素....