全排列题解

题目 全排列I

题目链接 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

实现思路

经典回溯问题，dfs深度遍历 图片来源leetcode题解

代码

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> answers = new ArrayList<>(); List<Integer> lists = new ArrayList<>(); int[] visited = new int[nums.length]; //判空处理 if (nums.length == 0 || nums == null) { return answers; } backtracking(nums, visited, lists, answers); return answers; } public void backtracking(int[] nums, int[] visited, List<Integer> lists, List<List<Integer>> answers) { //结束条件 if (lists.size() == nums.length) { //结果集 answers.add(new ArrayList<>(lists)); return; } //循环保证加入每个元素 for (int i = 0; i < nums.length; i++) { //当前元素被选择，有这条路径 则跳过 if (visited[i] == 1) { continue; } //没有则选择这个元素 并且加入路径 visited[i] = 1; lists.add(nums[i]); //递归 进入下层决策树 backtracking(nums, visited,lists, answers); //回溯 取消选择状态 清除路径 visited[i] = 0; lists.remove(lists.size() - 1); } } }

题目 全排列II

题目链接 给定一个可包含重复数字的序列，返回所有不重复的全排列。 示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

实现思路

在原全排列的基础上 进行去重 利用HashSet即可 虽然不优化

代码

class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Set<List<Integer>> answers = new HashSet<>(); List<Integer> lists = new ArrayList<>(); int[] isvisited = new int[nums.length]; if (nums == null || nums.length == 0) { return new ArrayList<>(answers); } backtracking(nums, isvisited, lists, answers); List<List<Integer>> res=new ArrayList<>(answers); return res; } public void backtracking(int[] nums, int[] isvisited, List<Integer> lists, Set<List<Integer>> answers) { if (lists.size() == nums.length) { answers.add(new ArrayList<>(lists)); return; } for (int i = 0; i < nums.length; i++) { if (isvisited[i] == 1) { continue; } isvisited[i] = 1; lists.add(nums[i]); backtracking(nums, isvisited,lists, answers); isvisited[i] = 0; lists.remove(lists.size() - 1); } } }