华为OD面试手撕真题 - 全排列 (C++ Python JAVA JS GO)-程序员充电站

这道题出现的频率非常高，几个小伙伴都反馈抽到这道题。

题目描述

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例一

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例二

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例三

输入：nums = [1] 输出：[[1]]

提示

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums中的所有整数互不相同

题解

力扣原题链接

思路:递归回溯

总体思路：有n个位置，每个位置尝试放置不同数，从而达到获取所有排列方式。前面的位置选择的数，后面的位置不能在选择。
通过1的思路进行拆解
- 要想每个位置尝试放置不同数：实现很简单，使用循环遍历原数组就行，每个数都尝试放入就行。
- 要想实现前面的位置选择的数，后面的位置不能在选择。,使用一个bool数组，进行去重就行。
经过1 2 的逻辑分析之后，接下来就是递归回溯的基本套路实现就行。递归的终止条件为所有位置都已填充数。

使用下面代码的时间复杂度为O(n * n!)

c++

class Solution { public: void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& res, vector<bool>& visited) { int n = nums.size(); // 全部数字已放入 if (path.size() == n) { res.push_back(path); return ; } for (int i = 0; i < n; i++) { // 已被之前位置选择 if (visited[i]) { continue; } // 递归回溯 path.push_back(nums[i]); visited[i] = true; dfs(nums, path, res, visited); visited[i] = false; path.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { int n = nums.size(); vector<vector<int>> res; vector<bool> visited(n, false); vector<int> path; dfs(nums, path, res, visited); return res; } };

JAVA

import java.util.*; class Solution { // DFS 生成全排列 private void dfs(int[] nums, List<Integer> path, boolean[] visited, List<List<Integer>> res) { int n = nums.length; // 所有数字都已放入路径 if (path.size() == n) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < n; i++) { // 已被之前位置选择 if (visited[i]) { continue; } visited[i] = true; path.add(nums[i]); dfs(nums, path, visited, res); // 回溯 path.remove(path.size() - 1); visited[i] = false; } } public List<List<Integer>> permute(int[] nums) { int n = nums.length; List<List<Integer>> res = new ArrayList<>(); boolean[] visited = new boolean[n]; List<Integer> path = new ArrayList<>(); dfs(nums, path, visited, res); return res; } }

Python

fromtypingimportListclassSolution:defpermute(self,nums:List[int])->List[List[int]]:res=[]n=len(nums)visited=[False]*n# DFS 生成全排列defdfs(path):# 所有数字都已放入路径iflen(path)==n:res.append(path[:])returnforiinrange(n):# 已被之前位置选择ifvisited[i]:continuevisited[i]=Truepath.append(nums[i])dfs(path)# 回溯path.pop()visited[i]=Falsedfs([])returnres

JavaScript

varpermute=function(nums){constn=nums.length;constres=[];constvisited=newArray(n).fill(false);constpath=[];// DFS 生成全排列functiondfs(){// 所有数字都已放入路径if(path.length===n){res.push([...path]);return;}for(leti=0;i<n;i++){// 已被之前位置选择if(visited[i])continue;visited[i]=true;path.push(nums[i]);dfs();// 回溯path.pop();visited[i]=false;}}dfs();returnres;};

Go

funcpermute(nums[]int)[][]int{n:=len(nums)res:=make([][]int,0)visited:=make([]bool,n)path:=make([]int,0,n)// DFS 生成全排列vardfsfunc()dfs=func(){// 所有数字都已放入路径iflen(path)==n{tmp:=make([]int,n)copy(tmp,path)res=append(res,tmp)return}fori:=0;i<n;i++{// 已被之前位置选择ifvisited[i]{continue}visited[i]=truepath=append(path,nums[i])dfs()// 回溯path=path[:len(path)-1]visited[i]=false}}dfs()returnres}