Problem

Given a list of arrays arrays, return all combinations where each combination picks exactly one element from each input array. This is the Cartesian product of the input arrays.

Examples

Example 1

1
2

Input: arrays = [[1,2,3], [4], [5,6]]
Output: [[1,4,5], [1,4,6], [2,4,5], [2,4,6], [3,4,5], [3,4,6]]

Example 2

1
2

Input: arrays = [["a","b"], ["x","y"]]
Output: [["a","x"],["a","y"],["b","x"],["b","y"]]

Constraints & notes

  • Input arrays may be empty; if any input array is empty the result is an empty list.
  • Sizes of arrays may vary; total number of combinations equals the product of the input sizes.
  • Order of combinations does not matter unless a specific order is required by the caller.

Solution

Two common approaches are: (1) recursive backtracking that builds combinations in-place, and (2) iterative expansion that folds arrays into the running result.

Method 1 — Backtracking (DFS)

Intuition

Treat each input arrays[i] as a decision point: choose one element from arrays[i] and recurse to fill the rest. This is like walking down a tree of depth m (number of arrays) where each level branches by the size of the corresponding array.

Approach

  • If arrays is empty, return [] (or [[]] depending on convention); for our purposes, if any array is empty return [].
  • Maintain a temporary curr list of length m to hold the current choice.
  • Define dfs(i) which fills curr[i] by iterating over items in arrays[i]:
    • If i == m, append a copy of curr to ans and return.
    • For each v in arrays[i]: set curr[i] = v and call dfs(i+1).
  • Start with dfs(0) and return ans.

Edge cases: if any arrays[i] is empty return [] early; handle m == 0 by returning [].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
  vector<vector<int>> permutationsOfArrays(const vector<vector<int>>& arrays) {
    int m = arrays.size();
    for (auto &a : arrays) if (a.empty()) return {};
    vector<int> curr(m);
    vector<vector<int>> ans;
    function<void(int)> dfs = [&](int i) {
      if (i == m) { ans.push_back(curr); return; }
      for (int v : arrays[i]) {
        curr[i] = v;
        dfs(i+1);
      }
    };
    if (m == 0) return {};
    dfs(0);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package main

func permutationsOfArrays(arrays [][]int) [][]int {
	m := len(arrays)
	for _, a := range arrays {
		if len(a) == 0 {
			return [][]int{}
		}
	}
	if m == 0 { return [][]int{} }
	curr := make([]int, m)
	var ans [][]int
	var dfs func(int)
	dfs = func(i int) {
		if i == m {
			tmp := make([]int, m)
			copy(tmp, curr)
			ans = append(ans, tmp)
			return
		}
		for _, v := range arrays[i] {
			curr[i] = v
			dfs(i+1)
		}
	}
	dfs(0)
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;

class Solution {
	public List<List<Integer>> permutationsOfArrays(List<List<Integer>> arrays) {
		int m = arrays.size();
		for (List<Integer> a : arrays) if (a.isEmpty()) return Collections.emptyList();
		if (m == 0) return Collections.emptyList();
		List<Integer> curr = new ArrayList<>(Collections.nCopies(m, 0));
		List<List<Integer>> ans = new ArrayList<>();
		dfs(arrays, 0, curr, ans);
		return ans;
	}

	private void dfs(List<List<Integer>> arrays, int i, List<Integer> curr, List<List<Integer>> ans) {
		if (i == arrays.size()) { ans.add(new ArrayList<>(curr)); return; }
		for (int v : arrays.get(i)) {
			curr.set(i, v);
			dfs(arrays, i+1, curr, ans);
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  fun permutationsOfArrays(arrays: List<List<Int>>): List<List<Int>> {
    val m = arrays.size
    arrays.forEach { if (it.isEmpty()) return emptyList() }
    if (m == 0) return emptyList()
    val curr = MutableList(m) { 0 }
    val ans = mutableListOf<List<Int>>()
    fun dfs(i: Int) {
      if (i == m) { ans.add(curr.toList()); return }
      for (v in arrays[i]) {
        curr[i] = v
        dfs(i+1)
      }
    }
    dfs(0)
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def permutations_of_arrays(self, arrays: list[list[int]]) -> list[list[int]]:
        m = len(arrays)
        for a in arrays:
            if not a:
                return []
        if m == 0:
            return []
        curr: list[int] = [0] * m
        ans: list[list[int]] = []

        def dfs(i: int) -> None:
            if i == m:
                ans.append(curr.copy())
                return
            for v in arrays[i]:
                curr[i] = v
                dfs(i+1)

        dfs(0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

pub struct Solution;
impl Solution {
    pub fn permutations_of_arrays(arrays: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = arrays.len();
        if arrays.iter().any(|a| a.is_empty()) || m == 0 { return Vec::new(); }
        let mut curr = vec![0; m];
        let mut ans: Vec<Vec<i32>> = Vec::new();
        fn dfs(arrays: &Vec<Vec<i32>>, i: usize, curr: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            if i == arrays.len() { ans.push(curr.clone()); return }
            for &v in &arrays[i] {
                curr[i] = v;
                dfs(arrays, i+1, curr, ans);
            }
        }
        dfs(&arrays, 0, &mut curr, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

export class Solution {
  permutationsOfArrays(arrays: number[][]): number[][] {
    const m = arrays.length
    if (arrays.some(a => a.length === 0) || m === 0) return []
    const curr = new Array<number>(m).fill(0)
    const ans: number[][] = []
    function dfs(i: number) {
      if (i === m) { ans.push(curr.slice()); return }
      for (const v of arrays[i]) {
        curr[i] = v
        dfs(i+1)
      }
    }
    dfs(0)
    return ans
  }
}

Complexity

  • ⏰ Time complexity: O(m * Π_{i=0..m-1} s_i) where m is number of arrays and s_i is the size of arrays[i] — there are Π s_i combinations and building each combination costs O(m).
  • 🧺 Space complexity: O(Π_{i} s_i * m) to store output; auxiliary recursion stack O(m).

Method 2 — Iterative expansion (folding)

Intuition

Start with res = [[]] and for every input array append each element to each partial combination in res. After processing all arrays, res contains every combination.

Approach

  • Initialize res = [[]].
  • For each arr in arrays:
    • Build next = [].
    • For each partial t in res and each v in arr, append t + [v] to next.
    • Set res = next.
  • Return res (if any arr is empty return []).

Code (Python example)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def permutations_of_arrays_iter(arrays: list[list[int]]) -> list[list[int]]:
  if not arrays: return []
  if any(not a for a in arrays): return []
  res: list[list[int]] = [[]]
  for arr in arrays:
    nxt: list[list[int]] = []
    for t in res:
      for v in arr:
        nxt.append(t + [v])
    res = nxt
  return res

Complexity

  • ⏰ Time complexity: O(m * Π_i s_i) for the same reasons as Method 1.
  • 🧺 Space complexity: O(Π_i s_i * m) to hold the result; auxiliary O(1) beyond output if done carefully.