组合总和与回溯剪枝

/*
 * 题目：组合总和与回溯剪枝
 * 要求：输入可含重复值的正整数数组 candidates 和非负整数 target；每个数组位置最多选一次，返回和为 target 的所有不重复组合。每组内升序，组合列表按字典序排列；target=0 返回 [[]]，且不得修改输入。
 * 示例：candidates=[1,1,2]、target=2 返回 [[1,1],[2]]；两个值为 1 的位置可一起选，但相同数值组合只返回一次。
 */
function combinationSumOnce(candidates, target) {}
console.log(combinationSumOnce([10, 1, 2, 7, 6, 1, 5], 8)); // 预期：[ [1, 1, 6], [1, 2, 5], [1, 7], [2, 6], ]
console.log(combinationSumOnce([1, 1, 1], 2)); // 预期：[[1, 1]]
console.log(combinationSumOnce([2], 1)); // 预期：[]
console.log(combinationSumOnce([], 0)); // 预期：[[]]

function combinationSumOnce(candidates, target) {
  if (!Number.isInteger(target) || target < 0)
    throw new RangeError("target must be a non-negative integer");
  if (!candidates.every((value) => Number.isInteger(value) && value > 0))
    throw new RangeError("candidates must be positive integers");
  const values = [...candidates].sort((a, b) => a - b);
  const results = [];
  const path = [];

  function dfs(start, remaining) {
    if (remaining === 0) {
      results.push([...path]);
      return;
    }
    for (let i = start; i < values.length; i += 1) {
      if (i > start && values[i] === values[i - 1]) continue;
      if (values[i] > remaining) break;
      path.push(values[i]);
      dfs(i + 1, remaining - values[i]);
      path.pop();
    }
  }

  dfs(0, target);
  return results;
}

// 三组以上可直接运行的验证。
console.log(combinationSumOnce([10, 1, 2, 7, 6, 1, 5], 8)); // 预期：[ [1, 1, 6], [1, 2, 5], [1, 7], [2, 6], ]
console.log(combinationSumOnce([1, 1, 1], 2)); // 预期：[[1, 1]]
console.log(combinationSumOnce([2], 1)); // 预期：[]
console.log(combinationSumOnce([], 0)); // 预期：[[]]