46：全排列

LeetCode链接

给定一个不含重复数字的数组 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 中的所有整数 互不相同

自己的做法：用hashset来保存已经填过的数，防止重复

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result=new ArrayList<>();List<Integer> temp=new ArrayList<>();Set<Integer> set =new HashSet<>();if(nums==null||nums.length==0){return result;}dfs(nums,result,temp,set,nums.length);return result;}public void dfs(int[] nums,List<List<Integer>> result,List<Integer> temp,Set<Integer> set,int k){if(k==0){result.add(new ArrayList<Integer>(temp));return;}for(int i=0;i<nums.length;++i){if(!set.contains(i)){temp.add(nums[i]);set.add(i);dfs(nums,result,temp,set,k-1);set.remove(i);temp.remove(temp.size()-1);}}}
}

官方题解： 利用动态数组，将数组划分为左右两块，左边是已经放置好的数字，右边是还未放置的数字，递归处理，然后记得回溯，也就是当前位置要放别的数字了，那么就应该恢复之前的状态

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result=new ArrayList<>();List<Integer> temp=new ArrayList<>();if(nums==null||nums.length==0){return result;}for(int num:nums){temp.add(num);}dfs(nums,result,temp,0);return result;}public void dfs(int[] nums,List<List<Integer>> result,List<Integer> temp,int index){if(index==nums.length){result.add(new ArrayList<Integer>(temp));return;}for(int i=index;i<nums.length;++i){//将所选数字换到当前要填的位置上Collections.swap(temp,index,i);dfs(nums,result,temp,index+1);//回溯，重新把数字换回来，恢复初始状态Collections.swap(temp,index,i);}}
}

47 全排列II

LeetCode题解

给定一个可包含重复数字的序列 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

方法：
换用boolean数组来保存每个数字的访问状态，因为set的contains方法的时间复杂度虽然是O(1)，但是一直add和remove也挺费事的；另外47和46的区别在于这里的数组可能有重复数字，所以这里采用了在组合题40中的方法：对数组排序，然后将多个相同的字符看成同一个，一个位置放一次这个数字就可以了

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result=new ArrayList<>();List<Integer> temp=new ArrayList<>();boolean[] vis=new boolean[nums.length];if(nums==null||nums.length==0){return result;}Arrays.sort(nums);dfs(nums,result,temp,vis,nums.length);return result;}public void dfs(int[] nums,List<List<Integer>> result,List<Integer> temp,boolean[] vis,int k){if(k==0){result.add(new ArrayList<Integer>(temp));return;}for(int i=0;i<nums.length;++i){if(!vis[i]){temp.add(nums[i]);vis[i]=true;dfs(nums,result,temp,vis,k-1);//回溯vis[i]=false;temp.remove(temp.size()-1);while((i+1)<nums.length&&nums[i]==nums[i+1]){++i;}}}}
}

https://leetcode-cn.com/problems/subsets-ii/solution/90-zi-ji-iiche-di-li-jie-zi-ji-wen-ti-ru-djmf/
可以看下上面链接里说的关于去重的理解，去重是去的同一层的，而不是同一个树枝上的