回溯算法：leetcode 46 全排列

Jan 14, 2020 · 1 min read · Golang 回溯算法数组 ·

本文讲解了用最简单的递归方法来实现全排列以及背后的回溯算法思想。

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

示例1：

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

示例2：

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

提示：

1 \(\leq\) nums.length \(\leq\) 6
-10 \(\leq\) nums[i] \(\leq\) 10
nums 中的所有整数互不相同

思路：回溯模板：

 1func backtracking(参数){
 2  if 终止条件 {
 3    存放结果; 
 4    return;
 5  }
 6  for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
 7    处理节点; 
 8    backtracking(路径,选择参数)
 9    回溯,撤销处理结果;
10  }
11}

选择参数这里我们设定一个 boolArray, 每个 index 判断当前路径里面的元素是否已经收录。解法如下：

 1package main 
 2
 3import (
 4  "fmt"
 5)
 6var path []int
 7var result [][]int
 8
 9func permute(arr []int)[][]int{
10  var boolArr [len(arr)]bool
11  boolArr = [len(arr)]bool{false}
12  backtracking(arr,boolArr)
13  return result
14}
15
16func backtracking(arr []int, boolArr []bool){
17  if len(path) == len(arr){
18    rersult = append(result,path)
19    return
20  }
21  for (i := 0; i < len(arr); i++){
22    if boolArr[i] == true {continue}
23      boolArr[i] = true
24      append(path,arr[i])
25      backtracking(arr,boolArr)
26      path = path[:len(arr)-1]
27      boolArr[i] = false
28  }
29}
30
31func main(){
32  fmt.Println(permute([]int{1,2,3}))
33}

翻译:

"English" |