Combinations
Algorithm · Core
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.
When the order doesn't matter, it is a Combination.
When the order does matter it is a Permutation.
"My fruit salad is a combination of apples, grapes and bananas" We don't care what order the fruits are in, they could also be "bananas, grapes and apples" or "grapes, apples and bananas", its the same fruit salad.
Combinations without repetitions
This is how lotteries work. The numbers are drawn one at a time, and if we have the lucky numbers (no matter what order) we win!
No Repetition: such as lottery numbers (2,14,15,27,30,33)
Number of combinations
where n is the number of things to choose from, and we choose r of them,
no repetition, order doesn't matter.
It is often called "n choose r" (such as "16 choose 3"). And is also known as the Binomial Coefficient.
Combinations with repetitions
Repetition is Allowed: such as coins in your pocket (5,5,5,10,10)
Or let us say there are five flavours of ice cream:
banana, chocolate, lemon, strawberry and vanilla.
We can have three scoops. How many variations will there be?
Let's use letters for the flavours: {b, c, l, s, v}.
Example selections include:
{c, c, c}(3 scoops of chocolate){b, l, v}(one each of banana, lemon and vanilla){b, v, v}(one of banana, two of vanilla)
Number of combinations
Where n is the number of things to choose from, and we
choose r of them. Repetition allowed,
order doesn't matter.
Cheatsheet
 |  |
Made with okso.app
Code
/**
* @param {*[]} comboOptions
* @param {number} comboLength
* @return {*[]}
*/
export default function combineWithRepetitions(comboOptions, comboLength) {
if (comboLength === 0) {
return [[]];
}
if (comboLength < 0) {
return [];
}
// If the length of the combination is 1 then each element of the original array
// is a combination itself.
if (comboLength === 1) {
return comboOptions.map((comboOption) => [comboOption]);
}
// Init combinations array.
const combos = [];
// Remember characters one by one and concatenate them to combinations of smaller lengths.
// We don't extract elements here because the repetitions are allowed.
comboOptions.forEach((currentOption, optionIndex) => {
// Generate combinations of smaller size.
const smallerCombos = combineWithRepetitions(
comboOptions.slice(optionIndex),
comboLength - 1,
);
// Concatenate currentOption with all combinations of smaller size.
smallerCombos.forEach((smallerCombo) => {
combos.push([currentOption].concat(smallerCombo));
});
});
return combos;
}/**
* @param {*[]} comboOptions
* @param {number} comboLength
* @return {*[]}
*/
export default function combineWithoutRepetitions(comboOptions, comboLength) {
if (comboLength === 0) {
return [[]];
}
if (comboLength < 0) {
return [];
}
// If the length of the combination is 1 then each element of the original array
// is a combination itself.
if (comboLength === 1) {
return comboOptions.map((comboOption) => [comboOption]);
}
// Init combinations array.
const combos = [];
// Extract characters one by one and concatenate them to combinations of smaller lengths.
// We need to extract them because we don't want to have repetitions after concatenation.
comboOptions.forEach((currentOption, optionIndex) => {
// Generate combinations of smaller size.
const smallerCombos = combineWithoutRepetitions(
comboOptions.slice(optionIndex + 1),
comboLength - 1,
);
// Concatenate currentOption with all combinations of smaller size.
smallerCombos.forEach((smallerCombo) => {
combos.push([currentOption].concat(smallerCombo));
});
});
return combos;
}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.