LeetCode No46. 全排列 题解

• • • 一、题目
    • 二、解题思想
    • 三、代码
    • 四、复杂度分析
    • 五、算法评价

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

题目由于限制了每个元素不重复，因此大大降低了难度。

例如，对于 n 个无重复元素的集合 [a₁, a₂, … , a_n]，记其全排列为 P([a₁, a₂, … , a_n])。我们知道，全排列就是把每个元素不重复地排列起来，因此每个元素在每个位置上都需要出现。按照步骤，我们需要先将 [a₁, a₂, … , a_n] 先随机取一个放在第一个位置，例如我们先取 a₁：

" a 1 … … " "a_{1}dotsdots" "a1​……"

然后我们需要确定后面的序列，其实，后面 n - 1 的序列也就是对于 [a₂, a₃, … , a_n] 的全排列。即：

" a 1 " + P ( [ a 2 ,   a 3 ,   … ,   a n ] ) "a_{1}" + P([a_{2}, a_{3}, dots, a_{n}]) "a1​"+P([a2​, a3​, …, an​])

当然，这里我们只是把 a₁ 放在首位，我们还可以把 a₂ 放在首位，这样就是：

" a 2 " + P ( [ a 1 ,   a 3 ,   a 4 ,   … ,   a n ] ) "a_{2}"+P([a_{1}, a_{3}, a_{4}, dots, a_{n}]) "a2​"+P([a1​, a3​, a4​, …, an​])

因此，我们就可以得到以下的递推式：

P ( [ a 1 ,   a 2 ,   a 3 ,   … ,   a n ] ) = { " a 1 " + P ( [ a 2 ,   a 3 ,   … ,   a n ] ) " a 2 " + P ( [ a 1 ,   a 3 ,   … ,   a n ] ) … " a n " + P ( [ a 1 ,   a 2 ,   … ,   a n − 1 ] ) P([a_{1}, a_{2}, a_{3}, dots, a_{n}])= left{ begin{array}{l} "a_{1}" + P([a_{2}, a_{3}, dots, a_{n}])\ "a_{2}" + P([a_{1}, a_{3}, dots, a_{n}])\ dots\ "a_{n}" + P([a_{1}, a_{2}, dots, a_{n-1}]) end{array} right. P([a1​, a2​, a3​, …, an​])=⎩⎪⎪⎨⎪⎪⎧​"a1​"+P([a2​, a3​, …, an​])"a2​"+P([a1​, a3​, …, an​])…"an​"+P([a1​, a2​, …, an−1​])​

我们这里使用了递归的方式，递归出口可以设为：

P ( [ a ] ) = " a " P([a])="a" P([a])="a"

代码部分采用 for 循环和交换手段使得集合中每个元素都有机会放在第一个位置（起始位置），同时，后面的位置（第 2 到 n）不会出现第一个元素，这样就避免了集合 set 的使用。

// permutation : 存储全排列
// nums : 待全排列的无重复元素数组
// begin : 全排列的起始位置
// end : 终止位置
void partition(vector> &permutation, vector &nums, int begin, int end) {
    // 如果到达结束位置，将 nums 添加入 permutation，并结束返回
    // 递归出口
    if (begin == end) { permutation.push_back(nums); return; }
    
    // 将每个数字都放在起始位置各一遍
    for (int i = begin; i < end; ++i) {
        // 采用交换使得每个数字都有机会放在起始位置
        swap(nums[begin], nums[i]);
        
        // 换完后，计算后面的全排列
        partition(permutation, nums, begin + 1, end);
        
        // 计算完后，需要将原来互换的位置换回来，保留初始状态，进入下一操作
        swap(nums[begin], nums[i]);
    }
}

时间复杂度：

算法相当于构建了一颗排列树，时间复杂度为 O(n!)。

LeetCode 中：

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户

内存消耗：7.4 MB, 在所有 C++ 提交中击败了 93.28% 的用户

提交了很多次，整体时间稳定在 0 ~ 4 ms，内存消耗稳定在 7.3 ~ 7.5 ms。