13.6 Exercises¶
13.6.1 Concept Review¶
1. Will This Permutation Algorithm Miss Results?¶
A backtracking algorithm tries to generate all permutations using 1, 2, 3 in that order. Each time it chooses a number x, it:
- Appends
xto the current path. - Marks
xas "used." - Recursively fills the next position.
When the recursive call returns, the student removes only x from the end of the path and then tries the next number.
- Which permutation does the algorithm generate first? Can it still generate all 6 permutations?
- Before returning to the previous level, is removing only the last number from the path enough? If not, what else must be done? Explain why.
Answer
-
It first generates
[1, 2, 3], but it cannot generate all the permutations. Although the path becomes shorter when calls return, the markers for 1, 2, and 3 all remain "used," leaving no available number for later branches. -
It is not enough. After removing
xfrom the end of the path, the algorithm must also markxas "unused" again. The current path and the used markers together describe the search state. A choice changes both of them, so backtracking must restore both before another branch can choosexagain.
2. Does the Order of Choosing Numbers Matter?¶
You are given the sorted array [2, 3, 5] and target value 5. Each number may be chosen repeatedly.
The algorithm requires the numbers along each search path to appear only in nondecreasing order.
- Which distinct combinations can be found?
- Why is there no need to search for the same group of numbers in different orders? What does the nondecreasing-order restriction accomplish?
- Suppose the current path is
[3], the remaining amount is 2, and the next candidate is 3. Why can the algorithm stop checking all later candidates at this level?
Answer
-
The distinct combinations are
[2, 3]and[5]. -
This exercise treats
[2, 3]and[3, 2]as the same combination; the order in which numbers are selected does not create a different answer. Requiring numbers in a path to appear in nondecreasing order lets the search skip duplicate arrangements such as[3, 2]. -
The remaining amount is 2, while candidate 3 is already greater than 2. Because the array is sorted, all later candidates are even larger and cannot be added to the current combination, so the algorithm can stop checking this level immediately.
3. Where Can the Next Queen Be Placed?¶
Place queens row by row on a 4 × 4 chessboard, with both row and column indices starting at 0.
Queens have already been placed at (0, 1) and (1, 3). The next queen must be placed in row 2.
- Which columns are ruled out because they already contain a queen?
- Among the remaining columns, which positions are ruled out because they share a diagonal with an existing queen?
- Which positions in row 2 remain available to try?
Answer
-
Columns 1 and 3 already contain queens, so positions
(2, 1)and(2, 3)are ruled out. -
Among the remaining positions,
(2, 2)lies on the same diagonal as(1, 3), so it is also ruled out. Position(2, 0)shares neither a column nor a diagonal with either existing queen. -
The only position to try in row 2 is
(2, 0).This step shows only that the current placement is valid. If the board cannot be completed later, the algorithm must still backtrack and try an earlier alternative.
13.6.2 Programming Exercises¶
1. Permutations of Distinct Elements¶
The integer array nums contains at least one element, and all its elements are distinct.
List every possible order formed by using each element exactly once, and return each order as an array.
The permutations may appear in any order in the result.
Use backtracking, with a Boolean array recording whether the element at each position has already been selected for the current permutation.
Hints
- The recursion depth indicates which position of the permutation is currently being filled
- At each level, try only elements that have not yet been used
- When the path's length equals the length of
nums, add a copy of the path to the answer