POJ 2362 Square：木棒拼正方形的 DFS + 剪枝藝術

題目大意

給定 n (≤ 20) 根木棒，長度為正整數。問能否用所有木棒拼成一個正方形（不可折斷）。

必要條件（快速判斷 No）

1. 總長度 sum % 4 == 0，邊長 target = sum / 4。
2. 最長木棒 ≤ target。

核心算法：DFS 搜索 + 關鍵剪枝

將木棒降序排列，依次嘗試放入 4 條邊。
狀態：dfs(cur_len, start_idx, finished_sides)
- cur_len：當前正在拼的邊已湊到的長度
- start_idx：下一根木棒的搜索起始下標（避免排列重複）
- finished_sides：已拼好幾條邊（拼好 3 條第 4 條必成）

關鍵剪枝策略

1. 降序排列：優先放長木棒，失敗更快觸發回溯。
2. 拓撲序搜索：每次只從 start_idx 往後找，避免同一邊內木棒順序排列重複。
3. 跳過同長失敗木棒：若 stick[i] == stick[i-1] 且 i-1 未被使用/嘗試失敗，直接跳過 i。
4. 當前邊湊不滿時，若第一根木棒就放不進去，直接返回 false（對稱性剪枝）。
5. 拼好 3 條即成功：剩下的木棒總和必為 target，無需驗證第 4 條。

C++ 參考代碼

bool dfs(int cur_len, int start, int k) {
    if (k == 3) return true;  // 3 條拼好，第 4 條自動成形
    if (cur_len == target) return dfs(0, 0, k + 1);  // 開啟下一條邊

    int prev = -1;
    for (int i = start; i < n; ++i) {
        if (vis[i] || cur_len + sticks[i] > target || sticks[i] == prev) continue;
        vis[i] = true;
        if (dfs(cur_len + sticks[i], i + 1, k)) return true;
        vis[i] = false;
        prev = sticks[i];  // 記錄本層嘗試失敗的長度
        if (cur_len == 0) return false;  // 關鍵：第一根木棒放不進去，對稱性失敗
    }
    return false;
}

複雜度與實測

• 最壞指數級，但 n ≤ 20 且剪枝極強，實測毫秒級通過。
• 空間 O(n) 存訪問標記。

舉一反三

• 分成 k 等和子集（LeetCode 698）：同樣模板，k 為參數。
• 背包問題變體：若 n 較大但長度和較小，可用 DP 狀態壓縮。