精选力扣500题第28题 LeetCode 46. 全排列【c++ / java 详细题解】

àì夳堔傛蜴生んèń 2021-07-24 17:19 333阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、c++代码
         *  4、java代码

### 1、题目 ###

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

### 2、思路 ###

**(dfs)**  O ( n × n ! ) O(n×n!) O(n×n!)

**过程**

*  1、我们从前往后，一位一位枚举，每次选择一个没有被使用过的数。
 *  2、选好之后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。
 *  3、递归返回时，不要忘记将该数的状态改成“未被使用”，并将该数从相应位置上删除。

**递归搜索树**

我们以`1` ,`2` ,`3`为例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

### 3、c++代码 ###

class Solution { 
    public:
        vector<vector<int>> res;  //记录答案
        vector<bool> st;          //标记数组
        vector<int> path;         //记录路径
    
        vector<vector<int>> permute(vector<int>& nums) { 
     
            st = vector<bool>(nums.size(),false);
            path = vector<int>(nums.size());
    
            dfs(nums,0);
            return res;
        }
    
        void dfs(vector<int> &nums, int u)
        { 
            if( u == nums.size())
            { 
                res.push_back(path);
                return;
            }
            for(int i = 0; i < nums.size(); i++)
            { 
                if(!st[i]) //nums[i]可能为负数，因此这里我们标记下标
                { 
                    path[u] = nums[i];
                    st[i] = true;
                    dfs(nums,u+1);
                    st[i] = false;
                }
            }
        }
    };

### 4、java代码 ###

class Solution { 
        static List<List<Integer>> ans = new ArrayList<List<Integer>>();
        static boolean[] st;
        static List<Integer> t = new ArrayList<Integer>();
        static void dfs(int u,int[] nums)
        { 
            int n = nums.length;
            if(u == n)
            { 
                ans.add(new ArrayList<Integer>(t));
                return ;
            }
            for(int i = 0;i < n;i ++)
            { 
                if(st[i]) continue;
                t.add(nums[i]);
                st[i] = true;
                dfs(u + 1,nums);
                st[i] = false;
                t.remove(t.size() - 1);
            }
        }
        public List<List<Integer>> permute(int[] nums) { 
            ans.clear();
            int n = nums.length;
    
            st = new boolean[n + 10];
            dfs(0,nums);
            return ans;
        }
    }

**原题链接**：[46. 全排列][46.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/f40502a233be4d7a82d1dd3835d94d90.png
[46.]: https://leetcode-cn.com/problems/permutations/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/150d977aee2b48148b5f5e3218a8ed98.png