Generate all possible combinations of the list of lists

"""
Given k lists: list A, list B, list C, ... list K, generate all possible combinations of the list using all values of the list.
"""

def solve(lists: list[list]):
    """
    Time Complexity: O(m^n)
    Space Complexity: O(n * m^n)

    Where n is the number of input lists and m is the average length of each list.
    """

    # Handle the edge case where no lists are provided.
    if not lists:
        return [[]]  # Return a list with an empty combination.

    # If any list is empty, there can be no combinations.
    for lst in lists:
        if not lst:
            return []

    result = []

    def backtrack(index, current_combination):
        # If we've reached the end, add the current combination to the results.
        if index == len(lists):
            result.append(current_combination.copy())
            return
        # Iterate over each element in the current list.
        for element in lists[index]:
            current_combination.append(element)  # Choose an element.
            backtrack(index + 1, current_combination)  # Move to the next list.
            current_combination.pop()  # Backtrack to try the next element.

    backtrack(0, [])
    return result

lsts = [[1, 2], [3], [4, 5, 6]]
print(solve(lsts))