leetcode46.全排列

题目描述

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6

• -10 <= nums[i] <= 10

• nums 中的所有整数 互不相同

思路

• 在 子集 的基础上，不同的是排列只需要长度与nums相同的结果集，并且全排列不要用start来裁剪重复出现的数字，所以i:=0，used用来标记已经在一次已经存在的num。

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

    res:=[][]int{}
    memo:=[]int{}
    used:=make([]bool,len(nums))
    var backtrace func(used []bool)
    backtrace=func(used []bool){
        if len(memo)==len(nums){
            temp:=make([]int,len(memo))
            copy(temp,memo)
            res=append(res,temp)
        }

        for i:=0;i<len(nums);i++{
            if used[i]{
                continue
            }
            memo=append(memo,nums[i])
            used[i]=true
            backtrace(used)
            memo=memo[:len(memo)-1]
            used[i]=false
        }
    }
    backtrace(used)
    return res
}