这是一道 中等难度 的题

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

题目

给定一个不含重复数字的数组 $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=[1,2,3]$ 为例：

1. 递归函数：每次选取一个未曾选取过的元素，然后进入下一次递归。
2. 递归边界：当 $nums$ 中的所有元素都被选完时，记录答案，并返回。
3. 还原现场：每次回退时（红色箭头）应该将本次选择的元素删除。

Java 代码实现

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> selected = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {recursion( nums);return ans;}private void recursion( int[] nums){int n = nums.length;// 边界条件if(selected.size() == n){ans.add(new ArrayList(selected));return;}for(int i = 0; i < n; i++){if(selected.contains(nums[i])){continue;}selected.add(nums[i]);this.recursion( nums);selected.remove(selected.size() - 1);}}
}

Go 代码实现

var (ans [][]intselectedVal []intselectedIndex []bool
)func permute(nums []int) [][]int {ans = make([][]int, 0)selectedVal = make([]int, 0)selectedIndex = make([]bool, len(nums))recursion(nums)return ans
}func recursion(nums []int) {if len(selectedVal) == len(nums) {temp := make([]int, len(selectedVal))copy(temp, selectedVal)ans = append(ans, temp)return}for i, v :=  range nums{if selectedIndex[i]{continue}selectedIndex[i] = trueselectedVal = append(selectedVal, v)recursion(nums)selectedIndex[i] = false;selectedVal = selectedVal[:len(selectedVal) - 1]}
}