js实现组合
组合问题的基本概念
组合是指从一组元素中选出若干个元素，不考虑顺序。例如从数组 [1, 2, 3] 中选出 2 个元素，可能的组合为 [1,2], [1,3], [2,3]。
递归实现组合
递归是解决组合问题的经典方法，通过逐步缩小问题规模并合并结果：
function combinations(arr, k) {
if (k === 0) return [[]];
if (arr.length === 0) return [];
const first = arr[0];
const rest = arr.slice(1);
const withFirst = combinations(rest, k - 1).map(comb => [first, ...comb]);
const withoutFirst = combinations(rest, k);
return [...withFirst, ...withoutFirst];
}
// 示例用法
console.log(combinations([1, 2, 3], 2));
// 输出: [[1, 2], [1, 3], [2, 3]]迭代实现组合
使用位运算可以迭代生成所有可能的组合：
function combinationsIterative(arr, k) {
const result = [];
const n = arr.length;
for (let mask = 0; mask < (1 << n); mask++) {
if (countSetBits(mask) !== k) continue;
const current = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) current.push(arr[i]);
}
result.push(current);
}
return result;
}
function countSetBits(num) {
let count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count;
}
// 示例用法
console.log(combinationsIterative([1, 2, 3], 2));
// 输出: [[1, 2], [1, 3], [2, 3]]使用生成器实现组合
ES6 生成器可以惰性地生成组合，节省内存：
function* combinationsGenerator(arr, k, start = 0, current = []) {
if (current.length === k) {
yield [...current];
return;
}
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
yield* combinationsGenerator(arr, k, i + 1, current);
current.pop();
}
}
// 示例用法
const gen = combinationsGenerator([1, 2, 3], 2);
console.log([...gen]);
// 输出: [[1, 2], [1, 3], [2, 3]]处理大型数据集的优化
对于大型数据集，可以采用剪枝策略优化递归：
function optimizedCombinations(arr, k) {
const result = [];
function backtrack(start, path) {
if (path.length === k) {
result.push([...path]);
return;
}
const maxRemaining = arr.length - (k - path.length) + 1;
for (let i = start; i < maxRemaining; i++) {
path.push(arr[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}实际应用示例
从颜色列表中生成所有可能的双色组合：
const colors = ['red', 'green', 'blue', 'yellow'];
const colorPairs = combinations(colors, 2);
console.log(colorPairs);
// 输出: [['red', 'green'], ['red', 'blue'], ..., ['blue', 'yellow']]这些方法覆盖了从基础到进阶的组合生成需求，可以根据具体场景选择最适合的实现方式。递归方法直观但可能堆栈溢出，迭代方法适合确定性问题，生成器适合流式处理大数据集。
