解題說明
Beautiful Arrangement
題目描述:假設你有 n 個整數,分別是 1 到 n。若一個由這 n 個整數組成的排列,對每個位置 i(1-indexed)都滿足下列其中一個條件,則稱為「美麗排列」:
perm[i]能被i整除,或i能被perm[i]整除。
給定整數 n,回傳美麗排列的數量。
解題思路:使用回溯法逐位置(從位置 1 到 n)決定放哪個數字。在每個位置嘗試所有尚未使用的數字,若滿足整除條件則遞迴至下一位置,否則剪枝跳過。用一個整數 used(位元遮罩)追蹤已使用的數字,第 i 位為 1 表示數字 i+1 已使用,位元操作使已用數字的檢查與標記均為 O(1)。
由於 n ≤ 15,位元遮罩最多 15 位,結合回溯剪枝,實際搜尋空間遠小於 n!,效率極佳。也可搭配記憶化(memo[used] 記錄從當前位置開始的方案數),避免重複計算相同的 (position, used) 狀態。
C++ 解法
複雜度分析
時間複雜度:O(k),其中 k 為實際訪問的狀態數。最壞為 O(n!),但由於整除條件剪去大量分支,實際遠小於此;n=15 時約幾千個遞迴呼叫。若加記憶化,狀態數上界為 O(n × 2^n)。
空間複雜度:O(n)——遞迴深度為 n,每層使用 O(1) 額外空間(位元遮罩存於整數)。若加記憶化則為 O(n × 2^n)。
虛擬碼
1. Initialize count = 0.
2. Call backtrack(n, pos=1, used=0, count).
3. In backtrack(n, pos, used, count):
a. If pos > n: increment count and return.
b. For num from 1 to n:
- If bit (num-1) is set in used: skip.
- If num % pos == 0 OR pos % num == 0:
* Set bit (num-1) in used.
* Recurse: backtrack(n, pos+1, used, count).
* Unset bit (num-1) in used (implicit since used is passed by value).
4. Return count.其他解法
方法一:記憶化搜尋(Bitmask DP)
dp[mask] 表示「已放置的數字集合為 mask 時,從當前位置(= popcount(mask) + 1)開始能形成的美麗排列數」。狀態數 O(2^n),每個狀態 O(n) 轉移,整體 O(n × 2^n)。由於 n ≤ 15,2^15 = 32768,非常快。此法在 n 較大時更穩定,避免回溯的重複計算。
方法二:純暴力全排列
枚舉 1..n 的所有排列(用 next_permutation),對每個排列驗證所有位置是否滿足整除條件。時間複雜度 O(n! × n),n=15 時超過十兆次操作,完全不可行,但邏輯最清晰,適合理解題意。
方法三:迭代式 Bitmask DP(Bottom-up)
從空集合 mask=0 開始,逐步擴展:對每個 mask,確定下一個位置 pos = popcount(mask)+1,嘗試所有未在 mask 中且滿足整除條件的數字 num,更新 dp[mask | (1 << (num-1))]。不使用遞迴,適合避免函數呼叫開銷的場景。
延伸思考
- 若條件改為「perm[i] 與 i 互質(gcd(perm[i], i) == 1)」,回溯的合法性檢查應如何修改?預計答案數量會如何變化?
- n = 15 是本題的上限,若 n 增大到 20,記憶化搜尋的記憶體需求(O(2^20 × 20))是否仍然可接受?有什麼方法可以壓縮空間?
- 如何修改程式以輸出所有美麗排列本身(而非僅計數)?此時時間複雜度由什麼因素主導?