Skip to main content

46. Permutations

分析

经典回溯

go 在 map 和 slice 上是和JS类似的

Note that since both range and len treat a nil slice as a zero-length slice, these last two examples will work even if nobody likes cheese or bacon (however unlikely that may be).

参看

题解

func permute(nums []int) [][]int {

n := len(nums)
var dfs func(choosedMap map[int]bool, choosedPath []int)

ans := [][]int{}

dfs = func(choosedMap map[int]bool, choosedPath []int) {
if len(choosedPath) == n {
copyFromChoosedPath := make([]int, n)
copy(copyFromChoosedPath, choosedPath)
ans = append(ans, copyFromChoosedPath)
return
}

for _, num := range nums {
if choosedMap[num] {
continue
}
choosedMap[num] = true
choosedPath = append(choosedPath, num)
dfs(choosedMap, choosedPath)
choosedMap[num] = false
choosedPath = choosedPath[:len(choosedPath) - 1]
}
}

dfs(map[int]bool{}, []int{})

return ans
}