回溯算法解决全排列问题

package main

import (
    "fmt"
    "container/list"
)

var result *list.List
func ListDump(l *list.List) {
    for e:=l.Front();e!=nil;e=e.Next() {
        switch v:=e.Value.(type) {
        case int:
            fmt.Printf("%v\t",v)
        case *list.List:
            ListDump(v)
        default:
            fmt.Println("unknown type:%v", v)
        }   
    }
    
    fmt.Printf("----\n");
}



func ListCopy(l *list.List) *list.List {
    nl := list.New()
    for e:=l.Front();e!=nil;e=e.Next() {
        nl.PushBack(e.Value.(int))
    }

    return nl
}

func SliceCopy(o []int, idx int) []int {
    n := make([]int, idx)
    copy(n,o[:idx])
    n = append(n,o[idx+1:]...)
    return n
}


var result2 *list.List

func backtrack2(path *list.List, choices []int) {
    // 啥时候结束
    if len(choices)==0 {
        // 添加路径
        result2.PushBack(ListCopy(path))
        return
    }


    for i,v := range choices {
        //做选择
        left_choice := SliceCopy(choices,i)
        t := path.PushBack(v)
        //进入回溯
        backtrack2(path, left_choice)
        //撤销选择
        path.Remove(t)      
    }
}

func permute2(nums []int) {
    path := list.New()
    backtrack2(path, nums)
}

func main() {
    result2 = list.New()
    permute2([]int{1,2,3,4,5})
    ListDump(result2)
}