func permute(nums []int) [][]int {
n := len(nums)
var ans [][]int
var cur []int
st := make([]bool, n)
dfs(nums, n, &ans, 0, cur, st)
return ans
}
func dfs(nums []int, n int, ans *[][]int, depth int, cur []int, st []bool) {
if depth == n {
tmp := make([]int, len(cur))
copy(tmp, cur)
*ans = append(*ans, tmp)
return
}
for i := 0; i < n; i++ {
if !st[i] {
cur = append(cur, nums[i])
st[i] = true
dfs(nums, n, ans, depth+1, cur, st)
st[i] = false
cur = cur[:len(cur)-1]
}
}
}