⭐ 题目日期：

拼多多 - 2024/10/31

🌳 题目描述：

给定多个集合，从每个集合选一个数，组成一个新的集合，返回所有组合

例 1:
集合：[1, 2], [3, 4]
返回：[1, 3], [1, 4], [2, 3], [2, 4]

🕵🏽 面试评估：

这道题考查笛卡尔乘积，可以用递归回溯来解题，也可以使用乘积的思路，遍历所有可能的索引组合，生成对应的子集。

🧗 难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

递归回溯：

递归回溯可以形象地理解为一次“深度探索和回退”的过程，每次尝试所有可能性，并在合适的时候回溯。具体过程：

• 维持一个当前列表（currentList）：它用于记录当前路径的组合。当路径长度等于所有集合的数量时，这表示形成了一个完整的组合，将其加入最终结果 resultList。
• 深度探索：
  • 从第一个集合开始，每次从当前集合中选择一个元素，加入到 currentList。
  • 递归地进入下一个集合，继续选择元素并加入路径。
• 回溯处理：
  • 当完成了一个完整组合后，回退到上一步，将最近加入的元素移出 currentList。
  • 尝试当前集合中的其他元素，继续生成新的组合。
  • 如果当前集合的所有元素都尝试完毕，进一步回退到上一个集合，重复上述步骤。

例如：

• 初始时，currentList = []，从集合 1 中选择 1，currentList = [1]。
• 进入集合 2，选择 3，currentList = [1, 3]，加入结果列表。
• 回溯，移除 3，currentList = [1]，从集合 2 选择 4，currentList = [1, 4]，再次加入结果列表。
• 完成集合 2 的所有选择后，移除 1，回到集合 1，选择 2，currentList = [2]，继续上述流程。
• 如此往复，直到所有集合的元素都被组合过。

回溯的核心在于：每次尝试所有可能性并回退，确保覆盖每一种组合的可能性。

乘积思路：

如果有 n 个集合，且第 i 个集合的大小为 L(i)，那么总组合数为: total = L(0) * L(1) * ... * L(n - 1); 假设当前有一个笛卡尔积索引 index (0 <= index < total), 每个索引 index 可以拆分为各集合上的“局部索引”。对当前索引 index，对第一个集合取余，得到它在第一个集合中的位置。用整除法移除第一个集合的影响，继续对下一个集合重复上述过程。持续到最后一个集合。

💻代码：

递归回溯：

Java

public List<List<Integer>> subsetCombinations(List<List<Integer>> lists) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(lists, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(List<List<Integer>> lists, int index, List<Integer> current, List<List<Integer>> result) {
    if (index == lists.size()) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int number : lists.get(index)) {
        current.add(number);
        backtrack(lists, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

乘积思路：

Java

public List<List<Integer>> subsetCombinations(List<List<Integer>> lists) {
    List<List<Integer>> result = new ArrayList<>();
    int totalCombinations = 1;

    for (List<Integer> list : lists) {
        totalCombinations *= list.size();
    }

    for (int i = 0; i < totalCombinations; i++) {
        List<Integer> combination = new ArrayList<>();
        int currentIndex = i;

        for (List<Integer> list : lists) {
            // 计算当前集合的局部索引
            combination.add(list.get(currentIndex % list.size()));
            currentIndex /= list.size();
        }

        result.add(combination);
    }

    return result;
}

🚵🏻复杂度分析：

假设 n 个集合，第 i 个集合的长度为 L(i), 0 <= i < n;

时间复杂度：O(n * L(0) * L(1) * ... * L(n - 1))，遍历所有的组合

空间复杂度：O(n * L(0) * L(1) * ... * L(n - 1)), 存储所有的组合