❝
这是一道 「中等难度」 的题
https://leetcode.cn/problems/permutations/❞
题目
给定一个不含重复数字的数组 ，返回其 「所有可能的全排列」 。你可以 「按任意顺序」 返回答案。
示例 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]]
提示：
-
-
-
中的所有整数 「互不相同」
题解
这道题还是 「递归」 的思路，以示例一 为例：
-
递归函数：每次选取一个未曾选取过的元素，然后进入下一次递归。 -
递归边界：当 中的所有元素都被选完时，记录答案，并返回。 -
还原现场：每次回退时（红色箭头）应该将本次选择的元素删除。
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 [][]int
selectedVal []int
selectedIndex []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] = true
selectedVal = append(selectedVal, v)
recursion(nums)
selectedIndex[i] = false;
selectedVal = selectedVal[:len(selectedVal) - 1]
}
}
相关题目
可以使用递归解法的其他题目还有：
– End –
原文始发于微信公众号（i余数）：【算法题解】30. 全排列的递归解法
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193854.html
