---
tags: data_structure_python
---

# Cartesian product <img src="https://img.shields.io/badge/-easy-brightgreen">

Given `n` sets, compute the Cartesian product.

<ins>**Example:**</ins>

Input: # n = 3     
        sets = [
                [1,2,3],
                ['a','b','c'],
                [4,5]
              ]
Output: 
[
    [1, 'a', 4], [1, 'a', 5],
    [1, 'b', 4], [1, 'b', 5],
    [1, 'c', 4], [1, 'c', 5],
    [2, 'a', 4], [2, 'a', 5],
    [2, 'b', 4], [2, 'b', 5],
    [2, 'c', 4], [2, 'c', 5],
    [3, 'a', 4], [3, 'a', 5],
    [3, 'b', 4], [3, 'b', 5],
    [3, 'c', 4], [3, 'c', 5]
]

# Solution

### Solution 1: Recursive

def cartesian_product(i=0, sets, answers=[], partial=[]):
    if i == len(sets):
        answers.append(partial)
    else:
        for elt in sets[i]:
            cartesian_product(i+1, sets, answers, partial + [elt])
    return answers

### Solution 2: Iterative

def cartesian_product(sets):
    answers = [[]]
    for i in range(len(sets)):
        partial = []
        for res in answers:
            for elt in sets[i]:
                partial.append(res + [elt])
        answers = partial
    return answers