leetcode
leetcode 2901 ~ 2950
全排列

全排列

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 18 ms, 内存: 16.2 MB

/*
题目思路：
使用 Java Stream API 实现全排列问题。虽然使用 Stream 进行递归和回溯不太直观，但可以通过递归函数配合 flatMap 来实现。
*/

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SolutionStream {
    public List<List<Integer>> permute(int[] nums) {
        return permuteHelper(nums, new boolean[nums.length]);
    }

    private List<List<Integer>> permuteHelper(int[] nums, boolean[] used) {
        List<List<Integer>> results = new ArrayList<>();
        if (IntStream.of(used).allMatch(b -> b)) {
            results.add(new ArrayList<>());
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    List<List<Integer>> perms = permuteHelper(nums, used);
                    used[i] = false;
                    for (List<Integer> perm : perms) {
                        List<Integer> newPerm = new ArrayList<>();
                        newPerm.add(nums[i]);
                        newPerm.addAll(perm);
                        results.add(newPerm);
                    }
                }
            }
        }
        return results;
    }
}

解释

方法:

此题解采用了深度优先搜索（DFS）的方法来生成数组的所有可能全排列。递归函数 dfs 被用来尝试所有可能的元素组合。当递归的当前列表长度与输入数组长度相同时，说明形成了一个完整的排列，该排列被添加到结果列表中。在递归中，对输入数组中的每个元素进行遍历，如果元素已经存在于当前排列中，则跳过以避免重复使用；否则，将该元素添加到当前排列中，并继续递归。递归返回后，需要将最后添加的元素移除（回溯），以便尝试其他可能的元素添加。

时间复杂度:

O(n * n!)

空间复杂度:

O(n)

代码细节讲解

🦆
在DFS递归中，你是如何处理可能的重复元素，以确保每个元素只出现一次？
▷
在DFS递归函数中，通过检查当前元素是否已经存在于当前排列列表 `cur` 中来避免重复。在遍历输入数组 `nums` 的每个元素时，如果该元素已经在 `cur` 中，则跳过该元素的添加。这样确保了每个元素在每个全排列中只被使用一次。
🦆
递归函数中，为什么要使用cur.pop()进行回溯，这个操作的具体目的是什么？
▷
在递归函数中使用 `cur.pop()` 进行回溯是为了在探索完一个元素的所有排列可能后，移除该元素，从而回退到之前的状态。这样可以在不影响之前状态的基础上，尝试其他兄弟元素的排列组合。通过这种方式，我们能够探索完所有可能的排列组合，实现全排列。
🦆
您如何保证在dfs函数中，res列表的全排列是按照题目要求的任意顺序返回的？
▷
在DFS递归实现中，全排列的顺序由递归和元素添加的先后顺序决定。由于是深度优先搜索，递归将自然地探索每一种可能的排列，并按照探索到它们的顺序将它们添加到结果列表 `res` 中。这种方法不需要额外的操作来保证顺序，因为所有的排列都将在探索过程中自然生成，并按照生成的顺序返回，满足题目的要求。

相关问题

只出现一次的数字 II全排列 II