【LeetCode】46. 全排列

[WGrape]

题目介绍

https://leetcode-cn.com/problems/permutations/

思路

解题

package main

var list [][]int

func generate(nums []int, tmpArray []int, used []bool) {
	// 已经递归完成组成了所有的元素
	if len(tmpArray) == len(nums) {
                // 直接append会出现重复数据导致出错 ：list = append(list, tmpArray)
		part := make([]int, len(tmpArray))
		copy(part, tmpArray)
		list = append(list, part)
		return
	}

	// 遍历nums数组
	for index, n := range nums {
		if used[index] {
			continue
		}

		// 如果n未使用过, 则记录到临时数组中
		used[index] = true
		tmpArray = append(tmpArray, n)
		generate(nums, tmpArray, used)

		// 恢复为未使用状态
		used[index] = false
		tmpArray = tmpArray[:len(tmpArray)-1]
	}
}

func permute(nums []int) [][]int {
    list = nil
	generate(nums, make([]int, 0), make([]bool, len(nums)))
    return list
}

// fmt.Println(permute([]int{1, 2, 3, 4, 5}))

第一版代码

package main

import "fmt"

// 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
/*
  输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/

var list = make([][]int, 0)

func generate(nums []int, tmpArray []int, used []bool) {
	// 已经递归完成组成了所有的元素
	if len(tmpArray) == len(nums) {
		list = append(list, tmpArray)
		return
	}

	// 遍历nums数组
	for index, n := range nums {
		if used[index] {
			continue
		}

		// 如果n未使用过, 则记录到临时数组中
		used[index] = true
		tmpArray = append(tmpArray, n)
		generate(nums, tmpArray, used)

		// 恢复为未使用状态
		used[index] = false
		tmpArray = tmpArray[:len(tmpArray)-1]
	}
}

func main() {
	list = nil
	generate([]int{1, 2, 3, 4}, make([]int, 0), make([]bool, 4))

	fmt.Println(list)
}