给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
- 输入: [1,2,3]
- 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
全排列,顾名思义就是:Amn,结果刚开始的我想都没想就写出了空间O(n2)的算法。。。。
//错误示范
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
int[][] ans = new int[n][n];
for (int i = 0; i < n; ++i) {
int number = nums[i];
int index = i;
for (int j = 0; j < n; ++j) {
int[] arr = ans[j];
arr[index] = number;
index = (index + 1) % n;
}
}
for (int[] arr : ans) {
List<Integer> list = new ArrayList<>();
for (int number : arr) {
list.add(number);
}
result.add(list);
}
return result;
}
根据Anm,本来想用循环,填满一个int[Anm][Anm]的矩阵,再转化为二维List。
后来用手写模拟全排列枚举过程的时候,发现了规律,可见手写模拟的重要性:
对于当前的path,只要确定了当前需要添加的数字,那么这条path只要将nums里剩下的数字的全排列,依次拼接到path中,就完成的单层的回溯任务。
所以在当前回溯步骤中,对于拿到的数组nums,我们要依次挑选(遍历)所有的数字,并将删除了这个数字的子数组再传入下一层回溯树中,这就确定了参
由此回溯分析完成:
- 返回值:void——不需要,由外层的result收集结果
- 参数:List<Integer> nums——在当前回溯步骤中,对于拿到的数组nums,我们要依次挑选(遍历)所有的数字,并将删除了这个数字的子数组再传入下一层回溯树中
- 终止:path.size() == 初始数组的长度,则result.add();
- 单层逻辑:在当前回溯步骤中,对于拿到的数组nums,我们要依次挑选(遍历)所有的数字,并将数字加入path中,然后将删除了这个数字的子数组再传入下一层回溯树中
因此代码如下:
class Solution {
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
//原始数组的长度
int n = 0;
public List<List<Integer>> permute(int[] arr) {
n = arr.length;
//将原始数组处理成List,方便回溯时删除元素
List<Integer> nums = new ArrayList<>(n);
for (int i : arr) {
nums.add(i);
}
backtracking(nums);
return result;
}
private void backtracking(List<Integer> nums) {
if (path.size() == n) {
result.add((ArrayList) path.clone());
return ;
}
int i = 0;
for (Integer number : nums) {
path.add(number);
backtracking(delete(nums, i++));
path.remove(path.size()-1);
}
}
//用以删除List中具体索引的数,并返回一个新的list
private List<Integer> delete(List<Integer> nums, int index) {
List<Integer> ans = new ArrayList<>();
int i = 0;
for (Integer number : nums) {
if (i++ == index) {
continue;
}
ans.add(number);
}
return ans;
}
}
由此做 47.全排列 II 时,自然先用笔模拟了一下,发现了以下规律:
在全排列回溯时,当前回溯树层已经加入path的数不要再次加入,否则会产生重复
代码如下:
private void backtracking(List<Integer> nums){
if (path.size() == n) {
result.add((ArrayList) path.clone());
return ;
}
Set<Integer> set = new HashSet<>();
int i = -1;
for (Integer number : nums) {
++i;
//如果重复了,则直接跳过
if (set.contains(number)) {
continue;
} else {
set.add(number);
path.add(number);
backtracking(delete(nums, i));
path.remove(path.size()-1);
}
}
}