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/
可以看下上面链接里说的关于去重的理解，去重是去的同一层的，而不是同一个树枝上的