46. 全排列

骑猪看日落 2024-03-31 14:32 30阅读 0赞

> **一次一粒沙，一次一件事。**——《人性的优点》

### 46. 全排列 ###

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

#### 思路：（回溯：暴力遍历） ####

回溯万能模板：

void backtracking(/* 所需参数（访问标记, 中间存储, 最终存储, 原始数据）*/) {
    		// TODO 自动生成的方法存根
    		if(/*终止条件*/) {
    			//一种情况，加入最终存储
    			return; //返回
    		}
    		for(/*对现有条件进行罗列*/) {
    			if(/*判断是否合理，或者是否已访问*/) {
    				continue;//跳过
    			}
    			//将该元素加入中间存储（修改条件）
    			//标位已访问
    			backtracking(/*参数*/); //递归调用自身
    			//将该元素从中间存储删除（条件复位，即 ：回溯）
    			//标记为未访问
    		}
    	}

本题注意点：ArrayList是一个引用类型，因此每次都要new一个再加入到list中

#### 代码： (Java) ####

import java.util.ArrayList;
    import java.util.List;
    
    public class arrangement {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        1, 2, 3};
    		System.out.println(permute(nums));
    	}
    	public static List<List<Integer>> permute(int[] nums) {
        
    		List<List<Integer>> alarr = new ArrayList<>();
    		List<Integer> midarr = new ArrayList<>();
    		boolean [] hasVisited = new boolean [nums.length];
    		if(nums == null || nums.length == 0) {
        
    			return alarr;
    		}
    		backtracking(hasVisited, midarr, alarr, nums);
    		return alarr;
    	}
    	private static void backtracking(boolean[] hasVisited, List<Integer> midarr, List<List<Integer>> alarr, int[] nums) {
        
    		// TODO 自动生成的方法存根
    		if(midarr.size() == hasVisited.length) {
        
    			alarr.add(new ArrayList<>(midarr));//重新构造一个 List
    			return;
    		}
    		int n = hasVisited.length;
    		for(int i = 0; i < n; i++) {
        
    			if(hasVisited[i]) {
        
    				continue;
    			}
    			midarr.add(nums[i]);
    			hasVisited[i] = true;
    			backtracking(hasVisited, midarr, alarr, nums);
    			midarr.remove(midarr.size() - 1);
    			hasVisited[i] = false;
    		}
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][c3910407d4704532b9d787bc6fcc848d.png]

#### 其他同等解法的题目： ####

[257. 二叉树的所有路径][257.]  
[79. 单词搜索][79.]  
[93. 复原 IP 地址][93. _ IP]  
[17. 电话号码的字母组合][17.]  
[47. 全排列 II][47. _ II]

##### 注：仅供学习参考！ #####

题目来源：[力扣][Link 1]

[c3910407d4704532b9d787bc6fcc848d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e1ef6aea88a244c38d04ae6d3532e6a3.png
[257.]: https://blog.csdn.net/weixin_43412762/article/details/128148704?spm=1001.2014.3001.5502
[79.]: https://blog.csdn.net/weixin_43412762/article/details/128131522?spm=1001.2014.3001.5502
[93. _ IP]: https://blog.csdn.net/weixin_43412762/article/details/128114845?spm=1001.2014.3001.5502
[17.]: https://blog.csdn.net/weixin_43412762/article/details/128097224?spm=1001.2014.3001.5502
[47. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128172523?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128172523%22%2C%22source%22%3A%22weixin_43412762%22%7D
[Link 1]: https://leetcode.cn/problems/permutations/description/