Cartesian Product
Algorithm · Stretch
Step through it: Backtracking pattern
holding [ ]
Step 1 of 7
Goal: list every subset of [1, 2]. At each number we choose: take it or skip it. All the choices form a tree of decisions. Start with nothing chosen.
Step 2 of 7
Choose to take 1.
Step 3 of 7
Take 2 as well. No numbers are left, so write this subset down.
Step 4 of 7
Undo that last choice (the "back" in backtracking) and skip 2 instead. Write [1] down.
Step 5 of 7
Undo taking 1 and skip it instead: holding [ ] again.
Step 6 of 7
From [ ], take or skip 2 the same way: [2] and [ ]. The four leaves are every subset. The recipe is choose, explore, undo. If a choice breaks a rule, stop that branch early (pruning).
Step 7 of 7
Your turn.
In set theory a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
Cartesian product AxB of two sets A={x,y,z} and B={1,2,3}
Code
/**
* Generates Cartesian Product of two sets.
* @param {*[]} setA
* @param {*[]} setB
* @return {*[]}
*/
export default function cartesianProduct(setA, setB) {
// Check if input sets are not empty.
// Otherwise return null since we can't generate Cartesian Product out of them.
if (!setA || !setB || !setA.length || !setB.length) {
return null;
}
// Init product set.
const product = [];
// Now, let's go through all elements of a first and second set and form all possible pairs.
for (let indexA = 0; indexA < setA.length; indexA += 1) {
for (let indexB = 0; indexB < setB.length; indexB += 1) {
// Add current product pair to the product set.
product.push([setA[indexA], setB[indexB]]);
}
}
// Return cartesian product set.
return product;
}References
Practice
Backtracking
- Binary Tree PathsEasy
- SubsetsMedium
- Subsets IIMedium
- PermutationsMedium
- Permutations IIMedium
- CombinationsMedium
- Combination SumMedium
- Combination Sum IIMedium
- Combination Sum IIIMedium
- Letter Combinations of a Phone NumberMedium
- Generate ParenthesesMedium
- Palindrome PartitioningMedium
- Word SearchMedium
- Restore IP AddressesMedium
- Letter Case PermutationMedium
- Partition to K Equal Sum SubsetsMedium
- N-QueensHard
- Sudoku SolverHard
- Word Break IIHard
- Expression Add OperatorsHard
Spotted a mistake or something unclear? Report it on GitHub.