Where it runs
1. The problem
You need to put 2 people on call out of a group of 4. You want to list every possible pair, so you can compare them. Here the pair {Ann, Bob} is the same as {Bob, Ann}: the same two people are on call. The order means nothing.
If you reuse the order search from the last lesson, you get {Ann, Bob} and {Bob, Ann} as two separate results, and then you have to remove the repeats. For pairs that is a small job. When you choose 5 people out of 30, each group appears 120 times: the search produces 17,100,720 orders for 142,506 different groups. A choice where order does not matter is called a combination. You can list each combination exactly once, with no cleanup of repeats.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- generate all subsets/permutations/combinations
- n is small (roughly n <= 12-20), exponential search is acceptable
- make a choice, recurse, then undo it before trying the next choice
- place items under constraints and back off on conflict (N-Queens, Sudoku)
- return every valid arrangement, not just one
Looks similar, isn't
- Recursion
Recursion goes down and comes back. Backtracking also puts the state back as it returns.
- Recursion with memoization
A cache pays off when arguments repeat. Down a path of distinct choices they rarely do.
- Dynamic programming (1-D)
DP counts or optimises without listing anything. Backtracking is for when you need the arrangements.
- Matrix word search (grid DFS/backtracking)
That is this pattern on a grid. The choice there is which neighbour to step into.
The output is exponential, so n stays small. Subsets of 20 items are 1e6, permutations of 10 are 3.6e6.
On LeetCode
Problems that choose groups where order does not matter, often with a target sum. Pass a start index down so each group is built in one order only.
The lesson task under the same name.
Choose k numbers from 1 to 9 with start, and stop a branch once the sum passes the target.
Recurse with the same start instead of start plus one, because a number may be reused.
Sort, use each number once, and skip a value equal to the one before it at the same level.