NC+LC：全排列
无重复项
题目描述
给定一个不含重复数字的数组nums，返回其 所有可能的全排列 。
LeetCode中可按任意顺序返回答案，但牛客要求以数字在数组中的位置靠前为优先级，按字典序排列输出。
示例
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路
实现代码1
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>(); //结果集合
List<Integer> list = new ArrayList<>();
for(int num : nums){ //将数组元素存入集合，直接对该集合进行处理
list.add(num);
}
backtrack(res, nums.length, list, 0);
return res;
}
public void backtrack(List<List<Integer>> res, int length, List<Integer> list, int start) {
if (start == length) { //递归终止条件，遍历到了数组末尾
res.add(new ArrayList<Integer>(list)); //需新建一个集合对象存入
return;
}
for (int i = start; i < length; i++) {
//将start上的元素依次与后面的元素进行交换
Collections.swap(list, start, i);
//递归
backtrack(res, length, list, start+1);
//回溯上一个start的位置，保证与其他位置进行同样的交换
Collections.swap(list, start, i);
}
}
} 实现代码2
使用类似深度优先遍历（DFS）的做法
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>(); //结果集合
int[] visited = new int[nums.length]; //标记访问过的位置
backtrack(res, nums, new ArrayList<Integer>(), visited);
return res;
}
public void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
if (tmp.size() == nums.length) { //递归终止条件
res.add(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] == 1) continue;
visited[i] = 1;
tmp.add(nums[i]);
//递归访问没访问过的位置
backtrack(res, nums, tmp, visited);
//在回溯过程中还原到上一状态
visited[i] = 0;
tmp.remove(tmp.size() - 1);
}
}
} 有重复项
LC 47.全排列 II：https://leetcode-cn.com/problems/permutations-ii/
题目描述
给定一个可包含重复数字的序列nums，按任意顺序 返回所有不重复的全排列。
示例
输入：nums = [1,1,2] 输出：[[1,1,2],[1,2,1],[2,1,1]]
思路
回溯法（在题目LC 46.全排列的基础进行修改，修改1：先将数组进行排序，使重复元素聚集在一起；修改2：接着通过判断当前元素与前一个元素是否相等，且前一元素是否被访问过来决定是否进行排列）
重点代码：
if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0){
continue;
} 实现代码
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>(); //结果集合
int[] visited = new int[nums.length]; //标记访问过的位置
Arrays.sort(nums); //排序，这样重复元素会聚集在一起
backtrack(res, nums, new ArrayList<Integer>(), visited);
return res;
}
public void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
if (tmp.size() == nums.length) { //递归终止条件，遍历到了数组末尾
res.add(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < nums.length; i++) {
//若当前元素与前一个元素相等，且前一元素未被访问过，就直接跳过，避免重复排列
if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0){
continue;
}
if(visited[i] == 0){
visited[i] = 1;
tmp.add(nums[i]);
//递归访问没访问过的位置
backtrack(res, nums, tmp, visited);
//在回溯过程中还原到上一状态
visited[i] = 0;
tmp.remove(tmp.size() - 1);
}
}
}
} 