从零学算法46

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

• 典型的全排列问题，直接套回溯算法模板就行，每次从剩余的数字中挑选一个添加到数组，用 boolean[] selected 记录某个数是否已被使用

•   List<List<Integer>> res = new ArrayList<>();
    int[] nums;
    boolean[] selected;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        selected = new boolean[nums.length];
        dfs(new ArrayList<>());
        return res;
    }
    public void dfs(List<Integer> list){
    	// 根据当前 list 长度判断是否已经完成一种组合
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        // 找出没被使用过的数字添加到 list 进行递归
        for(int i=0;i<nums.length;i++){
            if(selected[i])continue;
            selected[i]=true;
            list.add(nums[i]);
            dfs(list);
            list.remove(list.size() - 1);
            selected[i]=false;
        }
    }
  

• 同样使用回溯算法，还能用交换数组的值的方式来实现。比如长度为 3 的数组 [1,2,3]，第 1 位和第 2，3 位都试着交换位置，这样也就等于得到了每个第一位确定的结果即 [1xx,2xx,3xx]，在各自基础上继续同理交换能得到 [12x,13x,21x,23x,32x,31x]，其实到这里就可以确定组合方式，因为最后一个数字是已经确定了的，比如 12x 必定为 123

•   List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, 0);
        return res;
    }
    public void dfs(int[] nums, int index){
        //到最后一个数字，不用再交换了，直接把数组转化为list
        if (index == nums.length - 1) {
            //把数组转为list
            List<Integer> tempList = new ArrayList<>();
            for (int num : nums)
                tempList.add(num);
            //把list加入到res中
            res.add(tempList);
            return;
        }
        // 因为要顺着之前的基础交换，所以注意 i 从 index 开始
        for(int i=index;i<nums.length;i++){
        	// 交换
            swap(nums,index,i);
            dfs(nums,index+1);
         	// 换回来
            swap(nums,index,i);
        }
    }
    //交换两个数字的值
    private void swap(int[] nums, int i, int j) {
        if (i != j) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }
  

• 递归：假如我们要得到 [1,2,3] 的全排列，如果我们得到了 [2,3] 的全排列，那么我们只需要把最后的 1 试着放入不同的位置的即可，比如 [2,3] 全排列为 [23,32]，我们根据 23 可以得到 [123, 213, 231]，对 32 同理操作，最终就得到了我们想要的结果。
• 即我们会得到 [3] -> [23,32]->[…]

•   public List<List<Integer>> permute(int[] nums) {
        return helper(nums, 0);
    }
    
    /**
     * @param nums
     * @param index 递归当前数字的下标
     * @return
     */
    private List<List<Integer>> helper(int[] nums, int index) {
        List<List<Integer>> res = new ArrayList<>();
        //递归的终止条件，如果到最后一个数组，直接把它放到res中
        if (index == nums.length - 1) {
            //创建一个临时数组
            List<Integer> temp = new ArrayList<>();
            //把数字nums[index]加入到临时数组中
            temp.add(nums[index]);
            res.add(temp);
            // 要从例子中的 [3] 开始返回上一层处理了
            return res;
        }
        //处理过程，计算后面数字的全排列，第一次来这是从 [3] 开始
        List<List<Integer>> subList = helper(nums, index + 1);
        //集合中每个子集的长度
        int count = subList.get(0).size();
        //遍历集合subList的子集（或者说遍历 [xxx] 的全排列，比如遍历 [2,3] 的全排列 [23,32]）
        for (int i = 0, size = subList.size(); i < size; i++) {
            //把当前数字nums[index]添加到子集的每一个位置
            for (int j = 0; j <= count; j++) {
                List<Integer> temp = new ArrayList<>(subList.get(i));
                temp.add(j, nums[index]);
                res.add(temp);
            }
        }
        // 例子中第一次来这会返回 [23,32]，然后返回上一层同样处理
        return res;
    }