做印刷品的素材网站,上海网站制作公司哪,如何添加网站为信任站点,淘宝网站怎么做特价文章目录 46. 全排列题目描述回溯算法 46. 全排列
题目描述
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1#xff1a; 输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],… 文章目录 46. 全排列题目描述回溯算法 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] 10nums 中的所有整数 互不相同
回溯算法
class Solution {
public:vectorvectorint permute(vectorint nums) {vectorbool used(nums.size(), false); // 创建一个布尔数组用来标记nums中的元素是否被使用过backtracking(nums, used); // 调用回溯函数开始递归return result; // 返回最终的全排列结果}private:vectorvectorint result; // 用来存储所有的排列组合vectorint path; // 用来存储当前的排列组合// 回溯函数void backtracking(vectorint nums, vectorbool used) {// 如果当前的排列组合长度等于nums的长度说明找到了一个完整的排列if (path.size() nums.size()) {result.push_back(path); // 将当前排列加入到结果列表return; // 返回上一层递归}// 遍历nums的每个元素for (int i 0; i nums.size(); i) {// 如果当前元素已经被使用过跳过if (used[i] true) continue;// 否则标记当前元素为已使用used[i] true;// 将当前元素加入到当前排列组合path.push_back(nums[i]);// 继续递归填充剩下的元素backtracking(nums, used);// 回溯即撤销前面的选择path.pop_back(); // 移除当前排列的最后一个元素used[i] false; // 将当前元素标记为未使用以便于下一次循环能够使用}}
};代码的核心逻辑是回溯算法它通过递归来试探和回撤在每一步尝试不同的数值并在填满一种排列后将其加入结果集中然后撤销最后的选择回到上一步再尝试其他未被选择的数值。这个过程一直持续到所有的数都尝试过为止。
used数组用来标记某个数字是否已经在当前的排列中被使用过以避免产生重复的排列。path用来存放当前正在构建的排列。result用来存放所有可能的排列。
整个算法的时间复杂度为O(n*n!)其中n为数组nums的长度。因为有n!阶乘个排列而生成每个排列需要O(n)的时间。
