13.6 練習¶
13.6.1 知識鞏固¶
1. 這段排列演算法會漏掉結果嗎¶
一個回溯演算法按 1、2、3 的順序嘗試生成全部排列。每次選擇數字 x 時，它會：
- 把
x加到當前路徑末尾； - 把
x標記為“已使用”； - 遞迴填寫下一個位置。
遞迴返回後，同學只從路徑末尾刪除了 x，然後繼續嘗試下一個數字。
- 演算法首先得到哪個排列？它還能得到全部 6 個排列嗎？
- 遞迴返回上一層前，只刪除路徑末尾的數字是否足夠？如果不夠，還需要做什麼？說明理由。
參考答案
-
它首先得到
[1, 2, 3]，但無法得到全部排列。雖然返回時路徑變短了， 數字 1、2、3 的標記仍都是“已使用”，後續分支便沒有可選數字。 -
不夠。刪除路徑末尾的
x後，還必須把x重新標記為“未使用”。 當前路徑和已使用標記共同描述搜尋狀態；選擇時修改了兩處，回退時也必須把兩處都恢復， 其他分支才能再次選擇x。
2. 數字的選擇順序重要嗎¶
給定排好序的陣列 [2, 3, 5] 和目標值 5，每個數可以重複選擇。
演算法規定每條搜尋路徑中的數字只能按從小到大的順序出現。
- 能得到哪些不同的組合？
- 為什麼同一組數字不需要按不同順序重複搜尋？“從小到大”的限制起到了什麼作用？
- 當前路徑為
[3]、還差 2 時，下一個候選數是 3。為什麼此時可以停止檢查這一層後面的所有候選數？
參考答案
-
不同的組合為
[2, 3]和[5]。 -
本題把
[2, 3]和[3, 2]看作同一種組合，數字的選擇順序不計入答案。 規定路徑中的數字從小到大出現，就能在搜尋時直接跳過[3, 2]這類重複組合。 -
當前還差 2，而候選數 3 已經大於 2。因為陣列已經排好序， 3 後面的候選數只會更大，也都不可能加入當前組合，所以可以直接結束這一層的檢查。
3. 下一枚皇后可以放在哪些位置¶
在一個 4 × 4 棋盤上按行放置皇后，行、列下標都從 0 開始。
目前已經在 (0, 1) 和 (1, 3) 放置了皇后，現在要在第 2 行放置下一個皇后。
- 哪些列會因為“同列”而被排除？
- 在剩餘列中，哪些位置會因為“同一條對角線”而被排除？
- 第 2 行還剩哪些位置可以嘗試？
參考答案
-
第 1 列和第 3 列已經有皇后，因此位置
(2, 1)和(2, 3)被排除。 -
在剩餘位置中，
(2, 2)與(1, 3)位於同一條對角線上，因此也被排除。 位置(2, 0)與已有兩個皇后都不在同列或同一條對角線上。 -
第 2 行可以嘗試的位置只有
(2, 0)。這一步只說明當前放置合法；之後若無法完成棋盤，仍需回退並嘗試更早的其他選擇。
13.6.2 程式設計練習¶
1. 無重複元素的全排列¶
整數陣列 nums 至少包含一個元素，並且其中各元素互不相同。
請列出把這些元素各使用一次所能形成的全部順序，並將每一種順序作為一個陣列返回。
結果中各排列的先後次序不作要求。
請使用回溯，並用布林陣列記錄每個位置的元素是否已經選入當前排列。
解題提示
- 遞迴深度表示正在填寫排列中的第幾個位置
- 每一層只嘗試尚未使用的元素
- 路徑長度達到
nums的長度時，把它的副本加入答案
說明： 連結題解透過交換陣列元素，把已選元素依次放到陣列前部；本練習使用布林陣列記錄每個元素是否已選。兩種方法都能避免同一元素被重複選擇，但程式碼結構不同