第 29 讲：回溯与穷举搜索

func backtrack(path []T, state *State) {
    if isSolution(path) {
        record(path) // ⚠️ 若要保存，必须拷贝（见下）
        return
    }
    for _, choice := range candidates(state) {
        if !isValid(choice, state) {
            continue // ⭐ 剪枝：不合法就根本不进入
        }
        apply(choice, &path, state)   // 做选择
        backtrack(path, state)        // 递归
        undo(choice, &path, state)    // ⭐ 撤销
    }
}

res = append(res, path)                          // ✗ path 是切片，后续修改会污染已保存的结果
res = append(res, slices.Clone(path))            // ✓ 必须深拷贝
res = append(res, append([]int(nil), path...))   // ✓ 等价写法

func Subsets(nums []int) [][]int {
    var res [][]int
    var path []int

    var dfs func(start int)
    dfs = func(start int) {
        res = append(res, slices.Clone(path)) // 每个节点都是一个解
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            dfs(i + 1) // ⭐ i+1：每个元素最多用一次，且不回头 ⟹ 天然去重
            path = path[:len(path)-1] // 撤销
        }
    }
    dfs(0)
    return res
}

func Permutations(nums []int) [][]int {
    var res [][]int
    path := make([]int, 0, len(nums))
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            res = append(res, slices.Clone(path))
            return
        }
        for i := range nums {
            if used[i] {
                continue // 排列没有 start，改用 used 标记
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false // ⭐ 两个撤销都不能漏
        }
    }
    dfs()
    return res
}

func PermutationsUnique(nums []int) [][]int {
    slices.Sort(nums) // 前提：相同元素相邻
    var res [][]int
    var path []int
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            res = append(res, slices.Clone(path))
            return
        }
        for i := range nums {
            if used[i] {
                continue
            }
            // ⭐ 关键：同一层里，若前一个相同元素还没被用，说明我们正处在
            //    "跳过前一个、直接用后一个" 的分支上 —— 它与之前的分支重复
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}

func SolveNQueens(n int) int {
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n) // ↘ 方向：row - col + n 恒定
    diag2 := make([]bool, 2*n) // ↙ 方向：row + col 恒定
    count := 0

    var dfs func(row int)
    dfs = func(row int) {
        if row == n {
            count++
            return
        }
        for col := 0; col < n; col++ {
            d1, d2 := row-col+n, row+col
            if cols[col] || diag1[d1] || diag2[d2] {
                continue // ⭐ 剪枝：这一格被攻击
            }
            cols[col], diag1[d1], diag2[d2] = true, true, true
            dfs(row + 1)
            cols[col], diag1[d1], diag2[d2] = false, false, false // 撤销
        }
    }
    dfs(0)
    return count
}

func SolveNQueensBits(n int) int {
    count := 0
    full := (1 << n) - 1

    var dfs func(cols, d1, d2 int)
    dfs = func(cols, d1, d2 int) {
        if cols == full {
            count++
            return
        }
        // ⭐ 一次算出所有可放位置：取反后的空位
        avail := full &^ (cols | d1 | d2)
        for avail != 0 {
            p := avail & (-avail) // 取最低位的 1（第 20 讲的 lowbit）
            avail ^= p            // 用掉它
            dfs(cols|p, (d1|p)<<1&full, (d2|p)>>1)
            //          ↑ 对角线随行数下移而平移
        }
    }
    dfs(0, 0, 0)
    return count
}

if curCost + optimisticBound(remaining) >= best {
    return // 这条分支不可能更优
}

// 0-1 背包的分支限界：优先展开"乐观估计最大"的节点
type node struct {
    level, value, weight int
    bound                float64 // 乐观上界：用分数背包松弛计算
}

func knapsackBB(items []Item, W int) int {
    // 按单位价值降序排列，使分数背包松弛成为有效上界
    slices.SortFunc(items, func(a, b Item) int {
        return cmp.Compare(b.Value*a.Weight, a.Value*b.Weight)
    })
    pq := &nodeHeap{} // 最大堆，按 bound 排序
    heap.Push(pq, &node{level: -1, bound: fracBound(items, W, -1, 0, 0)})
    best := 0

    for pq.Len() > 0 {
        u := heap.Pop(pq).(*node)
        if u.bound <= float64(best) {
            continue // ⭐ 上界已不优于现有解，整棵子树剪掉
        }
        i := u.level + 1
        if i >= len(items) {
            continue
        }
        // 分支 1：取第 i 件
        if w := u.weight + items[i].Weight; w <= W {
            v := u.value + items[i].Value
            best = max(best, v)
            if b := fracBound(items, W, i, v, w); b > float64(best) {
                heap.Push(pq, &node{i, v, w, b})
            }
        }
        // 分支 2：不取第 i 件
        if b := fracBound(items, W, i, u.value, u.weight); b > float64(best) {
            heap.Push(pq, &node{i, u.value, u.weight, b})
        }
    }
    return best
}