NC+LC：全排列

无重复项

NC43 没有重复项数字的所有排列

LC 46.全排列：https://leetcode-cn.com/problems/permutations/

题目描述

给定一个不含重复数字的数组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);
        }
    }
}

有重复项

NC42 有重复项数字的所有排列

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);
            }
        }
    }
}