leetcode 46. 全排列

leetcode 46. 全排列

题目描述

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]] 示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3：

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

提示：

1 <= nums.length <= 6 -10 <= nums[i] <= 10 nums 中的所有整数 互不相同

解题思路

法1

回溯:\

1. 我们可以通过依次确定每一位的数值来解决这个题
   比如:输入1,2,3,4,5,6

2. 先确定第一位,有6种情况1/2/3/4/5/6

3. 将6种情况的数值作为数组的初始值与缺少该元素的数组一起传入下一个处理函数

(比如,假设第一位是2时,将传入一个2与数组[1,3,4,5,6]) 4. 下一步处理,
与开始的处理相似,就是确定下一位的数值,(比如第一位是2,那么下一位就有5种情况1/3/4/5/6)

5. 不断循环(所有可能的下一个值都要继续处理)递归方法(继续确定下一位的数值,直到唯一值的是否返回)

6. 记录所有路线的所有结果作为返回值,就可以得到最终的全排列数组了

• 时间复杂度(O(n^2))
• 空间复杂度(O(n^2))

执行结果

法1

func permute(nums []int) [][]int {
    var result [][]int
    backtrack(nums, []int{}, &result)
    return result
}

func backtrack(nums []int, current []int, result *[][]int) {
    if len(nums) == 0 {//满足结束条件, 将路径添加到结果列表中
        *result = append(*result, current)
        return
    }
    for i, num := range nums {
        nextNums := make([]int, len(nums)-1)//做出选择
        copy(nextNums[:i], nums[:i])//将选择加入路径中
        copy(nextNums[i:], nums[i+1:])//进入下一层决策树
        nextCurrent := append(current, num)
        backtrack(nextNums, nextCurrent, result)//回溯，撤销选择
    }
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.6 MB , 在所有 Go 提交中击败了 20.70% 的用户 通过测试用例： 26 / 26 炫耀一下: