📝个人主页:五敷有你
🔥系列专栏:算法分析与设计
⛺️稳中求进,晒太阳
题目
给定一个不含重复数字的整数数组
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]]
思路
- 回溯
这个问题可以看作是n个排列成一行的空格,我们需要从左向右填入给定的n个数,每个只能使用一次,那么很直接的可以想到穷举法,从左向右依次填入,看能不能填完这个n个空格,在这个过程可以使用回溯来模拟。
我们定义一个backtrack(first,output)表示从左向右填到first个位置,当前排列为output,那么整个递归函数分为两个情况:
一、first==n
这个情况就表示已经填完了n个位置,可以进行一次排列的收集
二、first<n
这个情况是从第一个格到first是固定了,之后就
之后first左边的固定了,右边的还在回溯。
first现在指向2,之后2和2自己进行交换,有人可能回想为什么2还要与自己进行交换,因为1 2 3 4 5 6 本身也是一种排列,难道不是吗?呼
然后first指向3,同理,自身与自身交换一次,然后一直回溯,。。。。
之后再回来回溯交换
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
代码实现:
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有数都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
}
}