Leetcode 47 全排列 II

题意理解：

        首先理解全排列是什么？全排列：使用集合中所有元素按照不同元素进行排列，将所有的排列结果的集合称为全排列。

        这里的全排列难度升级了，问题在于集合中的元素是可以重复的。

        问题：相同的元素会导致排列重复，需要对结果进行去重操作。

        难点：如何去重？

解题思路：

        排列可以用回溯方法来进行解决。可以将其解决方案抽象为一棵树结构。

        我们可以发现：

                当前枝当前层，选择到重复的元素时，后出现两个相同的树枝结构，造成相同的相同的重复的结果，所以去重应该剪枝：当前枝当前层重复元素的选择。——树层去重。

        为了实现树层去重：我们维护一个used[]数组来记录元素的访问状态。

        used数组的作用：        

                保证所有元素只是用一次。

                来辅助树层去重操作。

1.暴力回溯+剪枝优化

回溯解决问题的三个关键步骤：

        确定返回值和参数列表

        确定终止条件

        确定单层递归逻辑：1.保证元素只用一次  2.树层剪枝，防止重复值造成结果重复。

List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();boolean[] used=null;public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);used=new boolean[nums.length];//初始化默认值falsebacktracking(nums);return  result;}public void backtracking(int[] nums){//确定终止条件if(path.size()== nums.length){result.add(new ArrayList<>(path));return;}//单层递归逻辑for(int i=0;i<nums.length;i++){if(used[i]==true) continue;//该元素用过if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false) continue;//同枝同层剪枝path.add(nums[i]);used[i]=true;backtracking(nums);path.removeLast();used[i]=false;}}

2.分析

时间复杂度：O(n×n!)

空间复杂度：O(n)