算法详细实现package mainimport fmt/*生活场景回溯算法 Go 实现合集核心模板1. 做选择2. 递归进入下一层3. 撤销选择4. 尝试其它选择包含1. 聚餐座位安排排列 约束2. 100元买礼物组合 剪枝3. 房间分配分组 约束*/// // 示例1聚餐座位安排// 4个人围桌坐要求小明和小红不能相邻// func SeatArrangement() {people : []string{小明, 小红, 小刚, 小李}used : make([]bool, len(people))path : []string{}result : [][]string{}var backtrack func()valid : func(arr []string) bool {for i : 0; i len(arr)-1; i {if (arr[i] 小明 arr[i1] 小红) ||(arr[i] 小红 arr[i1] 小明) {return false}}return true}backtrack func() {// 结束条件4个人全部安排if len(path) len(people) {if valid(path) {temp : append([]string{}, path...)result append(result, temp)}return}for i : 0; i len(people); i {if used[i] {continue}// 做选择used[i] truepath append(path, people[i])// 递归探索backtrack()// 撤销选择path path[:len(path)-1]used[i] false}}backtrack()fmt.Println(座位方案, len(result))}// // 示例2100元购买3件礼物// 组合问题 金额剪枝// type Item struct {Name stringPrice int}func BuyGift() {items : []Item{{玩偶, 40},{书, 30},{巧克力, 20},{杯子, 25},{耳机, 60},{积木, 50},}path : []Item{}result : [][]Item{}var backtrack func(int, int)backtrack func(start int, sum int) {// 剪枝超过预算直接返回if sum 100 {return}// 选满3件if len(path) 3 {temp : append([]Item{}, path...)result append(result, temp)return}for i : start; i len(items); i {// 做选择path append(path, items[i])// 下一层backtrack(i1, sumitems[i].Price)// 撤销path path[:len(path)-1]}}backtrack(0, 0)fmt.Println(购买方案, len(result))}// // 示例3房间分配// 4个人住两个房间每间2人// 小明和小红不能同房// func RoomArrange() {people : []string{小明, 小红, 小刚, 小李}roomA : []string{}roomB : []string{}result : [][]string{}var backtrack func(int)check : func() bool {for _, a : range roomA {for _, b : range roomA {if (a 小明 b 小红) ||(a 小红 b 小明) {return false}}}return true}backtrack func(index int) {if index len(people) {if len(roomA) 2 len(roomB) 2 check() {result append(result,append([]string{}, roomA...),append([]string{}, roomB...))}return}// 选择放入房间Aif len(roomA) 2 {roomA append(roomA, people[index])backtrack(index1)roomA roomA[:len(roomA)-1]}// 选择放入房间Bif len(roomB) 2 {roomB append(roomB, people[index])backtrack(index1)roomB roomB[:len(roomB)-1]}}backtrack(0)fmt.Println(分房方案, len(result))}func main() {fmt.Println( 聚餐座位 )SeatArrangement()fmt.Println( 买礼物 )BuyGift()fmt.Println( 房间分配 )RoomArrange()}