Leetcode 46. 全排列 排列型回溯 C++实现

本文主要是介绍Leetcode 46. 全排列 排列型回溯 C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 46. 全排列

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

算法：

创建二维返回数组 ans ，和临时数组 path ，on_path 。

进入 dfs 函数，当 i==n 时，即已经排列完毕，则可以 return 。从 0 到 n 遍历，如果没选过就加入 path 中，并且将 on_path 设置成 true 表示该数字已经被挑选。进入下一层递归。下一层递归完毕返回该层后，将该层挑选的数字所对应的 on_path 重置（再次设置成 false ，即未被挑选状态），恢复现场。

代码：

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;// 返回数组ansint n = nums.size();vector<int> path(n),on_path(n);// 临时数组pathauto dfs = [&](auto &&dfs,int i){if(i == n){ans.emplace_back(path);return ;}for(int j = 0;j < n;j++){if(!on_path[j]){path[i] = nums[j];on_path[j] = true;dfs(dfs,i+1);on_path[j] = false;}}};dfs(dfs,0);// 递归入口return ans;}
};

这篇关于Leetcode 46. 全排列 排列型回溯 C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---