package utils;

import java.util.ArrayList;
import java.util.List;

public class Product {
	
	public static <T> List<List<T>> product(List<List<T>> lists) {
        List<List<T>> result = new ArrayList<>();
        
        if (lists == null || lists.isEmpty()) {
            return result;
        }

        backtrack(lists, result, 0, new ArrayList<>());
        return result;
    }

    private static <T> void backtrack(
            List<List<T>> lists,
            List<List<T>> result,
            int depth,
            List<T> current) {

        if (depth == lists.size()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (T element : lists.get(depth)) {
            current.add(element);
            backtrack(lists, result, depth + 1, current);
            current.remove(current.size() - 1);
        }
    }
	
}