LeetCode 算法：全排列 c++_业界新闻

发布时间:2024-07-18 00:22

阅读量: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 中的所有整数互不相同

全排列

全排列通常指的是从n个不同元素中取出所有元素，按照一定的顺序排列起来的所有可能的组合方式。如果不考虑重复元素，全排列的总数是 n!（n的阶乘），即 n x (n-1) x (n - 2) x ...x 2 x1。
例如，如果有三个不同的元素A、B和C，那么它们的全排列有：
ABC
ACB
BAC
BCA
CAB
CBA
全排列在数学、计算机科学和统计学等领域都有广泛的应用。在编程中，可以通过递归、回溯等算法来生成全排列。

回溯法

回溯法是一种通过试错来解决问题的算法策略，它尝试分步地去构造问题的解，当发现已经构造的部分解不可能是最终解的一部分时，就回退到上一步，尝试其他的可能。这种算法通常用于解决组合问题、排列问题、划分问题、图的着色问题等。
回溯法的基本思想是：
问题分解：将复杂问题分解成若干个简单的子问题。
路径：用一个候选解表示当前的路径，也就是到目前为止已经做出的选择。
选择：从当前问题的所有可能选择中选择一个，加入到候选解中。
扩展：尝试在加入选择后的候选解上进一步构造解。
剪枝：如果发现当前候选解不可能产生最终解，就回溯到上一步，放弃当前选择，并尝试其他选择。
停止条件：如果候选解已经满足问题的所有要求，就输出这个解。
回溯法的效率往往取决于剪枝的效率，也就是如何快速判断当前路径是否值得继续探索。在实际应用中，回溯法经常结合其他算法使用，比如回溯法结合动态规划、贪心算法等。
回溯法的实现通常使用递归函数，递归函数的参数包括当前候选解、当前位置等信息。递归的终止条件是候选解已经满足问题的所有要求或者当前位置已经超出了问题的范围。
回溯法的一个经典例子是八皇后问题，即在一个8x8的棋盘上放置8个皇后，使得它们互不攻击。这个问题可以通过回溯法来解决，通过递归尝试每一行放置皇后的位置，然后递归到下一行，直到找到所有可能的解。

题解

解题思路：回溯法

LeetCode上的全排列问题是一个经典的算法题目，通常用回溯算法来解决。以下是解决这个问题的一种通用思路：
定义递归函数：定义一个递归函数，该函数接收当前的排列数组和需要排列的数字范围。
递归终止条件：当排列数组的长度等于数字的范围时，说明已经生成了一个完整的排列，此时可以将这个排列添加到结果列表中。
回溯搜索：对于当前的数字范围，从起始数字开始，将每个数字添加到当前的排列数组中，并递归调用函数，将范围缩小到下一个数字。
回溯：在递归调用之后，需要撤销上一步的操作，即从当前排列数组中移除最后一个添加的数字，这样可以让下一个数字有机会被添加进来。
避免重复：如果数字有重复，需要在添加到排列数组之前检查该数字是否已经存在，以避免生成重复的排列。

c++ demo：

#include <iostream> #include <vector> #include <algorithm>  class Solution { public:     std::vector<std::vector<int>> permute(std::vector<int>& nums) {         std::vector<std::vector<int>> result;         backtrack(nums, 0, result);         return result;     }  private:     void backtrack(std::vector<int>& nums, int first, std::vector<std::vector<int>>& result) {         if (first == nums.size()) {             result.push_back(nums);             return;         }         for (int i = first; i < nums.size(); ++i) {             if (i != first && nums[i] == nums[first]) continue; // 跳过重复的数字             std::swap(nums[i], nums[first]);             backtrack(nums, first + 1, result);             std::swap(nums[i], nums[first]); // 回溯         }     } };  // 打印向量 void printVector(const std::vector<int>& vec) {     for (int num : vec) {         std::cout << num << " ";     }     std::cout << std::endl; }  int main() {     Solution solution;     std::vector<int> nums = { 1, 2, 3 };     std::vector<std::vector<int>> permutations = solution.permute(nums);      std::cout << "Permutations:" << std::endl;     for (const auto& perm : permutations) {         printVector(perm);     }      return 0; }