辽宁建设科技信息网网站,泗洪县建设局网站,东莞网站建设模具,做网站为什么要用源码1. 题目链接#xff1a;46. 全排列
2. 题目描述#xff1a; 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1#xff1a; 输入#xff1a;nums [1,2,3]
输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],…1. 题目链接46. 全排列
2. 题目描述 给定一个不含重复数字的数组 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] 10nums 中的所有整数 互不相同 3.解法递归
3.1 算法思路
典型的回溯题目我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式不断地枚举每个数在当前位置的可能性并且回溯到上一个状态直到枚举完所有的可能性得到正确的结果
每个数是否可能出现在当前位置只需要判断这个数在之前是否出现即可。
3.2 递归流程
首先定义一个二维数ret用来存放所有可能的排列一个一维数组path用来存放正在构建的排列路径一个一维数组用check来标记每个元素是否已经被使用过然后从第一个位置开始进行递归在每个递归的状态中我们维护一个步数path表示当前已经处理了几个数字递归结束条件当path等于nums数组的长度时说明我们已经处理完了所有数字将当前数组存入结果中在每个递归状态中枚举所有下标i若这个下标未被标记则使用nums数组中当前下标的元素 将check[i]标记为 true数组中第path个元素被nums[i]覆盖对第path1个位置进行递归将check[i]重新赋值为flase表示回溯 最后返回ret
特别地我们可以不使用标记数组直接遍历path之后的元素未被使用然后将其与需要递归的位置进行交换即可 3.3 C算法代码
class Solution {vectorvectorint ret; // 存储所有可能的排列结果vectorint path; // 当前正在构建的排列路径bool check[7]; // 标记数组用于记录每个元素是否已经被使用过public:vectorvectorint permute(vectorint nums) {dfs(nums); // 调用深度优先搜索函数进行全排列return ret; // 返回所有可能的排列结果}void dfs(vectorint nums) {if (nums.size() path.size()) { // 如果当前路径的长度等于输入数组的长度说明已经找到了一个排列ret.push_back(path); // 将当前路径添加到结果中return; // 结束当前递归分支}for (int i 0; i nums.size(); i) {if (!check[i]) { // 如果当前元素没有被使用过path.push_back(nums[i]); // 将当前元素添加到当前路径中check[i] true; // 标记当前元素已经被使用过dfs(nums); // 继续递归搜索下一个元素// 回溯操作path.pop_back(); // 移除当前路径中的最后一个元素check[i] false; // 标记当前元素未被使用过}}}
};
