关于leetcode:leetcode-46-Permutations-全排列中等

一、题目粗心

标签: 搜寻

https://leetcode.cn/problems/permutations

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

  二、解题思路

  应用回溯法解决此问题，对于每一个以后地位 i，咱们能够将其与之后的任意地位替换，而后持续解决地位 i +1，直到解决到最初一位。为了避免咱们每次遍历时都要新建一个子数组贮存地位 i 之前曾经替换好的数字，咱们就利用回溯法，只对原数组进行批改，在递归实现后再批改回来。

  三、解题办法

  3.1 Java 实现

  public class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans = new ArrayList<>();
        backTracking(nums, 0, ans);
        return ans;
    }
  
    void backTracking(int[] nums, int level, List<List<Integer>> ans) {if (level == nums.length - 1) {ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            return;
        }
        for (int i = level; i < nums.length; i++) {
            // 批改以后节点状态
            swap(nums, i, level);
            // 递归子节点
            backTracking(nums, level + 1, ans);
            // 回改以后节点状态
            swap(nums, i, level);
        }
    }
  
    void swap(int[] nums, int i, int j) {int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
  }

  四、总结小记

• 2022/6/3 在这天完结的时候实现