leetcode 46. Permutations 全排列 (中等)

作者：okokabcd

2022 年 6 月 03 日
本文字数：766 字
阅读完需：约 3 分钟

一、题目大意

标签: 搜索

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 在这天结束的时候完成

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/4c97879607fd9d3370bdb2032】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景