JavaScript实现含可选元素的数组组合生成函数求助

给定数组 keys = ["the?", "orange", "van", "s?"]，其中字符串末尾的?表示该元素为可选元素。需编写JavaScript函数generateCombinations(keys)，返回所有可能的组合，示例输出如下：
[["orange","van"],["the","orange","van"],["orange","van","s"],["the","orange","van","s"]]

可通过replace("?","")去除问号。尝试用递归实现但遇到问题，附上已编写的代码：

function isOptionalKey(key) {
    return key.endsWith('?');
}

function hasOptionalKey(keys) {
    return keys.some(isOptionalKey);
}

function stripOptionalSyntax(key) {
    return key.endsWith('?') ? key.slice(0, -1) : key;
}


function generateCombinations(keys) {
    if (keys.length === 1) {
        return keys;
    }

    const combinations = [];

    const startKey = keys[0];
    const restKeys = keys.slice(1);

    if (hasOptionalKey(restKeys)) {
        const restCombinations = isOptionalKey(startKey)
            ? generateCombinations(restKeys)
            : restKeys;

        if (isOptionalKey(startKey)) {
            combinations.push(restCombinations);
        }
        combinations.push(
            restCombinations.map((c) => [stripOptionalSyntax(startKey), ...c])
        );
    } else {
        if (isOptionalKey(startKey)) {
            combinations.push(restKeys);
        }
        combinations.push([stripOptionalSyntax(startKey), ...restKeys]);
    }

    return combinations;
}

你的递归思路方向正确，但原代码存在递归终止条件错误、组合结构合并混乱等问题。修正后的核心逻辑是：逐个处理元素，可选元素分「包含（去问号）」和「不包含」两种情况，必选元素仅保留「包含」情况，递归合并剩余元素的组合。

修正后的代码：

function isOptionalKey(key) {
    return key.endsWith('?');
}

function stripOptionalSyntax(key) {
    return isOptionalKey(key) ? key.slice(0, -1) : key;
}

function generateCombinations(keys) {
    // 递归终止：无元素时返回空组合作为基础
    if (keys.length === 0) {
        return [[]];
    }

    const firstKey = keys[0];
    const restCombinations = generateCombinations(keys.slice(1));
    const result = [];

    // 可选元素：添加「不包含当前元素」的组合
    if (isOptionalKey(firstKey)) {
        result.push(...restCombinations);
    }

    // 必选/可选元素通用：添加「包含当前元素」的组合
    const strippedKey = stripOptionalSyntax(firstKey);
    const withCurrent = restCombinations.map(comb => [strippedKey, ...comb]);
    result.push(...withCurrent);

    return result;
}

// 测试示例
const keys = ["the?", "orange", "van", "s?"];
console.log(generateCombinations(keys));
// 输出：[["orange","van"],["the","orange","van"],["orange","van","s"],["the","orange","van","s"]]

代码说明 #

1. 递归终止条件：当keys为空时返回[[]]，这是所有组合的基础，后续所有组合都基于这个空数组扩展。
2. 剩余组合递归：先获取剩余元素的所有可能组合，再基于此处理当前元素。
3. 可选元素分支：如果当前元素是可选的，直接把剩余元素的组合加入结果（对应「不选当前元素」的情况）。
4. 包含元素分支：无论元素是否可选，都生成「包含当前元素（去问号）」的组合，将处理后的元素添加到剩余组合的每个数组开头，再加入结果。

内容的提问来源于stack exchange，提问作者Siddharth Ganesh