演算法：多個 List 笛卡兒積組合生成 (全排列/全組合)

問題定義

輸入 m 個 List，第 i 個 List 大小 k_i。從每個 List 取一個元素組成新 List，共 k_1 * k_2 * ... * k_m 種組合。m 為動態參數，無法寫死巢狀迴圈。

解法一：遞迴回溯 (DFS)

void combine(List<List<T>> lists, int idx, List<T> current, List<List<T>> result) {
    if (idx == lists.size()) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (T elem : lists.get(idx)) {
        current.add(elem);
        combine(lists, idx + 1, current, result);
        current.remove(current.size() - 1);
    }
}

解法二：迭代法 (基於索引陣列)

List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> result = new ArrayList<>();
    int[] indices = new int[lists.size()];
    while (true) {
        List<T> combo = new ArrayList<>();
        for (int i = 0; i < lists.size(); i++)
            combo.add(lists.get(i).get(indices[i]));
        result.add(combo);
        // 進位邏輯
        int pos = lists.size() - 1;
        while (pos >= 0 && ++indices[pos] == lists.get(pos).size())
            indices[pos--] = 0;
        if (pos < 0) break;
    }
    return result;
}

解法三：Java 8 Stream (簡潔但記憶體較大)

lists.stream()
    .reduce(Stream.of(Collections.emptyList()),
        (acc, list) -> acc.flatMap(prefix -> list.stream().map(elem -> {
            List<T> n = new ArrayList<>(prefix); n.add(elem); return n;
        })),
        (a, b) -> a)
    .collect(Collectors.toList());

選擇建議

• 資料量小、追求可讀性：遞迴/Stream。
• 資料量大、需流式處理：迭代法配合 Iterator 逐個產出，避免全量記憶體。