做网站 需求怎么写,东莞十大公司排名,企业标志图片大全,方案案例网站力扣日记#xff1a;【回溯算法篇】46. 全排列 日期#xff1a;2023.2.21 参考#xff1a;代码随想录、力扣 46. 全排列
题目描述 难度#xff1a;中等 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1【回溯算法篇】46. 全排列 日期2023.2.21 参考代码随想录、力扣 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 中的所有整数 互不相同
题解
cpp ver
class Solution {
public:vectorint path;vectorvectorint result;int used[21] {0}; // 记录哪些值取过vectorvectorint permute(vectorint nums) {backtracking(nums);return result;}void backtracking(vectorint nums) {// 终止条件if (path.size() nums.size()) {result.push_back(path);return;}// for 横向遍历for (int i 0; i nums.size(); i) {// 需要标记哪些值已经取过了, nums[i] [-10, 10] - [0, 20] if (used[nums[i] 10] 1) continue; // 取过了则跳过该值// 否则标记取过并进行取值与递归used[nums[i] 10] 1;path.push_back(nums[i]);backtracking(nums);path.pop_back();used[nums[i] 10] 0;}}
};复杂度
时间复杂度: O(n!) 空间复杂度: O(n) 第一个取值有n个选择第二个有(n-1)个选择除去第一个以此类推总共 n*(n-1)*…*1n!种情况 思路总结
全排列本质上也是组合问题其特点是 全要求需要取到集合所有值才行到了叶子节点才能放入result排列则说明相同值但不同排序得到的组合是不同这样则要求在每次for循环时都需要从最前面开始遍历不需要之前组合和子集问题的startindex但这样需要考虑避免在纵向递归取到重复的值即要做到在for循环遍历时只有未取过的值才进行取值遍历。 关键是通过一个 used 数组哈希表记录取过的值即在for循环每次取值前判断当前值在 used中是否为1如果为1说明取过则跳过否则进行取值遍历和回溯。且每次取值后在used记录该值已取对应地要在回溯时置0。树状结构示意图from代码随想录 注used也可以用以下表示vectorbool used(nums.size(), false);
// 每次for循环取值后
used[i] true; // i 为for循环索引(与nums[i]同)
