全排列[回溯]
力扣top46 全排列1
题目：
给定一个不含重复数字的数组 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中的所有整数 互不相同
分析
本题可以使用回溯将所有可能得排列情况记录。
- 将当前数组分为左右两部分，左为已经选择并排列的部分，右为还没有选择排列的部分
[1 2|3 4] - 从未选择的部分中选择一个数放到 当前填充位（swap替换位置即可）
[1 2 3|4] - 然后继续递归直至填充完毕 将填充好的数组加入集合
list.add([1,2,3,4]) - 回溯，将swap交互的两个数再交换回来，然后选择下一个位置的数与 当前填充位替换
源代码
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>>list=new ArrayList<>();
backTracking(nums,list,0);
return list;
}
public void swap(int[] arr,int posA,int posB){
if(posA==posB)return;
int tmp=arr[posA];
arr[posA]=arr[posB];
arr[posB]=tmp;
}
public void backTracking(int[] nums,List<List<Integer>> list,int pos){
if(pos==nums.length){//边界
ArrayList<Integer>arr=new ArrayList<>();
for(int i:nums)arr.add(i);
list.add(arr);
}
for(int i=pos;i<nums.length;i++){
swap(nums,pos,i);
backTracking(nums,list,pos+1);
swap(nums,pos,i);
}
}
}
力扣top47 全排列2
题目：
给定一个含重复数字的数组 nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
nums中的所有整数 可能相同
分析
使用回溯将所有可能得排列情况记录。
-
将当前数组分为左右两部分，左为已经选择并排列的部分，右为还没有选择排列的部分
[1 2|3 4] -
从未选择的部分中选择一个数放到 当前填充位（swap替换位置即可）
只能选择未选择过的数字，使用
set来保证不选择重复数字，避免额外多余的排列[1 2 3|4] -
然后继续递归直至填充完毕 将填充好的数组加入集合
list.add([1,2,3,4]) -
回溯，将swap交互的两个数再交换回来，然后选择下一个位置的数与 当前填充位替换
源代码
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>>list=new ArrayList<>();
backTracking(nums,list,0);
return list;
}
public void swap(int[] arr,int posA,int posB){
int tmp=arr[posA];
arr[posA]=arr[posB];
arr[posB]=tmp;
}
public void backTracking(int[] nums,List<List<Integer>> list,int pos){
if(pos>=nums.length){
ArrayList<Integer>arr=new ArrayList<>();
for(int i:nums)arr.add(i);
list.add(arr);
return;
}
Set<Integer>set=new HashSet<>();
backTracking(nums,list,pos+1);
set.add(nums[pos]);
for(int i=pos+1;i<nums.length;i++){
if(set.contains(nums[i]))continue;
set.add(nums[i]);
swap(nums,pos,i);
backTracking(nums,list,pos+1);
swap(nums,pos,i);
}
}
}