精选50题之 46. 全排列

我不是女神ヾ 2024-04-18 19:06 51阅读 0赞

### 腾讯精选练习（50 题）之 46. 全排列 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  写在最后

## [原题目链接][Link 1] ##

给定一个没有重复数字的序列，返回其所有可能的全排列。

> 示例:  
> 输入: \[1,2,3\]  
> 输出:  
> \[  
> \[1,2,3\],  
> \[1,3,2\],  
> \[2,1,3\],  
> \[2,3,1\],  
> \[3,1,2\],  
> \[3,2,1\]  
> \]

## 题目分析 ##

由题目要求的的“返回其所有可能的全排列（解）”，可以想到回溯法。

回顾——  
[回溯法][Link 2]：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

## 解题分析 ##

与回溯法中的经典问题，求 **排列树** 的思路一致。  
Ps. 翻看笔记的时候发现，之前课上讲到回溯法时，只提到了子集树?（未涉及排列树）

具体分析如下，清晰明确  
by LeetCode  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]

## 代码实现 ##

class Solution {
        
    public:
        vector<vector<int>> permute(vector<int>& nums) {
        
            vector<vector<int>> res;
            backtrack(nums, res, 0);
            return res;
        }
            
            void swap(int &a, int &b)
            {
        
                int temp;
                temp = a;
                a = b;
                b = temp;
            }
            
            void backtrack(vector<int> &nums, vector<vector<int>> &res, int i)
            {
        
                if(i == nums.size())  // 初始化排列中的一种
                    res.push_back(nums);
                // 与 排序树 思路一致
                for(int j = i; j < nums.size(); j++)
                {
        
                    swap(nums[i], nums[j]);
                    backtrack(nums, res, i+1);
                    swap(nums[i], nums[j]);
                }
            }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]  
复杂度分析：

*  时间复杂度：略大于O(N!)
 *  空间复杂度：O(N!)

## 写在最后 ##

经典方法还是不熟练，温故知新。

[Link 1]: https://leetcode-cn.com/problems/permutations/
[Link 2]: https://baike.baidu.com/item/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95/9258495
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d1fd4ec7f04f4a3ea62c55d58df3a979.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2f15daee05064623aacd454d31f58e72.png