【刷题记录】46. 全排列-阿里云开发者社区

【刷题记录】46. 全排列

2022-05-31 97

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷题记录】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 中的所有整数 互不相同

二丶思路分析

**回溯** 比较典型的回溯问题，就不再说多了，直接开干

三、代码实现

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int length = nums.length;
        List<List<Integer>> res = new ArrayList<>();
if (length ==0) {
            return res;
        }
        boolean[] used = new boolean[length];
        List<Integer> path = new ArrayList<>();
        dfs(nums, length, 0, path, used, res);
        return res;
    }
    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
if (depth == len) {
            res.add(path);
            return;
        }
for (int i =0; i < len; i++) {
if (!used[i]) {
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);
                boolean[] newUsed = new boolean[len];
                System.arraycopy(used, 0, newUsed, 0, len);
                newUsed[i] =true;
                dfs(nums, len, depth +1, newPath, newUsed, res);
            }
        }
    }
}