当前位置：首页 > JavaScript

js实现凑数

2026-03-14 11:20:34JavaScript

凑数算法实现思路

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

递归回溯法

适用于小规模数据，通过深度优先搜索尝试所有可能的组合：

function findCombination(nums, target) {
  const result = [];

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

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

  backtrack(0, [], 0);
  return result;
}

动态规划法

适用于较大数据量，记录可能达到的和值：

function subsetSum(nums, target) {
  const dp = Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    for (let i = target; i >= num; i--) {
      dp[i] = dp[i] || dp[i - num];
    }
  }

  return dp[target];
}

近似算法

当需要快速找到近似解时，可采用贪心算法：

js实现凑数

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

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

  return { sum, combination: result };
}

优化建议

大数据集考虑使用记忆化递归
需要所有解时保留回溯过程中的路径
允许近似解时可设置误差范围
负数处理需要额外条件判断

实际应用示例

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

console.log('精确解:', findCombination(numbers, target));
console.log('是否存在解:', subsetSum(numbers, target));
console.log('近似解:', approximateSum(numbers, target));

以上方法可根据具体需求选择使用，递归法适合获取所有解，动态规划适合判断解是否存在，贪心算法适合快速获取近似解。

标签: js