目录
全排列
访问量:809

一、简介

题目:全排列-46

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

二、实现

func permute(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }

    res := make([][]int, 0)

    doPermute(nums, []int{}, &res)

    return res
}

// 每次进行循环,nums中需要排查 curList中已经存在的元素
func doPermute(nums []int, curList []int, res *[][]int) {
   if len(nums) == 0 {
        // 这个地方需要注意一下,不能直接将 curList 添加到 res,因为后面可能会改变curList中的元素
        newList := make([]int, len(curList))
        copy(newList, curList)
        *res = append(*res, newList)
        return
    }
    
    
    for i:=0; i< len(nums); i++ {
        curList = append(curList, nums[i])
        if i == 0 {
            doPermute(nums[1:], curList, res)
        } else if i == len(nums) - 1 {
            doPermute(nums[:len(nums) -1], curList, res)
        } else {
            newNums := make([]int, 0)
            newNums = append(newNums, nums[0:i]...)
            newNums = append(newNums, nums[i+1:]...)

            doPermute(newNums, curList, res)
        }
        // 回溯
        curList = curList[:len(curList) -1]
    }
}