当前位置：首页 > JavaScript

js实现凑数

2026-02-01 12:33:23JavaScript

实现凑数的基本思路

凑数问题通常指从给定数组中找出若干元素，使其和等于或接近目标值。以下是几种常见的实现方法：

递归回溯法

递归回溯是解决凑数问题的经典方法，适用于元素数量较少的情况：

js实现凑数

function findSubsets(arr, target) {
  const result = [];
  backtrack(arr, target, 0, [], result);
  return result;
}

function backtrack(arr, target, start, path, result) {
  if (target === 0) {
    result.push([...path]);
    return;
  }

  for (let i = start; i < arr.length; i++) {
    if (arr[i] > target) continue;
    path.push(arr[i]);
    backtrack(arr, target - arr[i], i + 1, path, result);
    path.pop();
  }
}

动态规划法

对于较大的数据集，动态规划更高效：

js实现凑数

function findSubsetsDP(arr, target) {
  const dp = Array(target + 1).fill().map(() => []);
  dp[0] = [[]];

  for (const num of arr) {
    for (let t = target; t >= num; t--) {
      for (const subset of dp[t - num]) {
        dp[t].push([...subset, num]);
      }
    }
  }

  return dp[target];
}

近似算法

当需要快速找到近似解时：

function approximateSubset(arr, target) {
  arr.sort((a, b) => b - a);
  let sum = 0;
  const result = [];

  for (const num of arr) {
    if (sum + num <= target) {
      sum += num;
      result.push(num);
      if (sum === target) break;
    }
  }

  return result;
}

性能优化建议

对于大规模数据，考虑以下优化：

先对数组进行降序排序
添加剪枝条件提前终止不必要的计算
使用记忆化技术存储中间结果

使用示例

const numbers = [3, 9, 8, 4, 5, 7, 10];
const target = 15;

console.log(findSubsets(numbers, target));
console.log(findSubsetsDP(numbers, target));
console.log(approximateSubset(numbers, target));

以上方法可根据实际需求选择使用，递归回溯适合精确解但时间复杂度高，动态规划适合中等规模数据，近似算法适合对精度要求不高的场景。

标签: js