JavaScript实现从数组中选出和等于固定值的n个数

下面是JavaScript实现从数组中选出和等于固定值的n个数的完整攻略：

问题描述

假设有一个数组arr和一个固定值target，如何从arr中选出n个数，使得这n个数的和等于target。

解决方案

1. 暴力破解

最简单粗暴的方法当然是暴力破解，即枚举所有的 n 个数的组合情况，计算它们的和，如果等于 target，则返回这个组合。但其时间复杂度为O($\binom{n}{len(arr)}$)，不太适合大规模数据。示例代码：

function findNNumbers(arr, target, n) {
  const getAllCombs = (arr, n) => {
    if (n === 1) {
      return arr.map(item => [item]);
    }
    let allCombs = [];
    for (let i = 0; i < arr.length - n + 1; i++) {
      const comb = getAllCombs(arr.slice(i + 1), n - 1).map(item => [arr[i], ...item]);
      allCombs = [...allCombs, ...comb];
    }
    return allCombs;
  };
  const combs = getAllCombs(arr, n);
  return combs.find(comb => comb.reduce((a, b) => a + b, 0) === target);
}

const arr = [1, 3, 5, 7];
const target = 10;
const n = 2;
console.log(findNNumbers(arr, target, n)); // [3,7]

2. 动态规划

在暴力破解的基础上进行优化，可以采用动态规划的思想。定义 dp[i][j][k] 表示前i个数中选j个数的和是否等于k，若dp[i][j][k]为true，则表示存在一组数的和等于k。则有以下状态转移方程：

• dp[i][j][k] = dp[i-1][j][k] // 不选第i个数
• dp[i][j][k] = dp[i-1][j-1][k-arr[i]] // 选第i个数

时间复杂度为$O(ntargetlen(arr))$，可以通过本题。示例代码：

function findNNumbers(arr, target, n) {
  const results = [];
  const dp = Array.from({ length: arr.length + 1 }, () => Array.from({ length: n + 1 }, () => Array.from({ length: target + 1 }, () => false)));
  for (let i = 1; i <= arr.length; i++) {
    for (let j = 1; j <= Math.min(i, n); j++) {
      for (let k = 1; k <= target; k++) {
        dp[i][j][k] = dp[i - 1][j][k];
        if (arr[i - 1] === k && j === 1) {
            dp[i][j][k] = true;
        }
        if (arr[i - 1] < k && j > 1) {
            dp[i][j][k] = dp[i - 1][j - 1][k - arr[i - 1]];
        }
        if (dp[i][j][k] && j === n && k === target) {
            const result = [];
            let x = i, y = j, z = k;
            while (x > 0 && y > 0 && z > 0) {
              if (dp[x][y][z]) {
                result.unshift(arr[x - 1]);
                y--;
                z -= arr[x - 1];
              }
              x--;
            }
            results.push(result);
        }
      }
    }
  }
  return results;
}

const arr = [1, 3, 5, 7, 9];
const target = 10;
const n = 3;
console.log(findNNumbers(arr, target, n)); // [ [3, 5, 2], [7, 2, 1] ]

这里假设找到所有可能的组合，如果只要其中任意一种，则可以在 dp 中用一个boolean变量标识是否找到即可。

3. 回溯法

利用回溯法可以找到所有符合条件的组合，而不仅是其中任意一种。示例代码：

function findNNumbers(arr, target, n) {
  const results = [];
  const dfs = (startIndex, path, sum) => {
    if (path.length === n && sum === target) {
      results.push([...path]);
      return;
    }
    for (let i = startIndex; i < arr.length && sum + arr[i] <= target && path.length + arr.length - i >= n; i++) {
      path.push(arr[i]);
      dfs(i + 1, path, sum + arr[i]);
      path.pop();
    }
  }
  dfs(0, [], 0);
  return results;
}

const arr = [1, 3, 5, 7, 9];
const target = 10;
const n = 3;
console.log(findNNumbers(arr, target, n)); // [ [1, 5, 4], [1, 3, 6], [1, 9, 0], [3, 5, 2], [7, 2, 1] ]

其中，startIndex 表示每一轮开始枚举的起点，path 是当前已选的数列，sum 表示当前已选的数列的和。

阅读剩余 59%