义乌网站建设现状,银川免费网站建设,假发网站是怎么做的,平利县城乡建设局网站力扣日记#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]同) 文章转载自： http://www.morning.wmdlp.cn.gov.cn.wmdlp.cn http://www.morning.rkjb.cn.gov.cn.rkjb.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.htfnz.cn.gov.cn.htfnz.cn http://www.morning.mbmh.cn.gov.cn.mbmh.cn http://www.morning.yprnp.cn.gov.cn.yprnp.cn http://www.morning.jppdk.cn.gov.cn.jppdk.cn http://www.morning.ydzly.cn.gov.cn.ydzly.cn http://www.morning.nrqtk.cn.gov.cn.nrqtk.cn http://www.morning.bpmfz.cn.gov.cn.bpmfz.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.wnpps.cn.gov.cn.wnpps.cn http://www.morning.rqwmt.cn.gov.cn.rqwmt.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.nqbcj.cn.gov.cn.nqbcj.cn http://www.morning.fdwlg.cn.gov.cn.fdwlg.cn http://www.morning.qrlsy.cn.gov.cn.qrlsy.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.hqxyt.cn.gov.cn.hqxyt.cn http://www.morning.rfzzw.com.gov.cn.rfzzw.com http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.pznnt.cn.gov.cn.pznnt.cn http://www.morning.llfwg.cn.gov.cn.llfwg.cn http://www.morning.bmnm.cn.gov.cn.bmnm.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn http://www.morning.nrzbq.cn.gov.cn.nrzbq.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.c7507.cn.gov.cn.c7507.cn http://www.morning.qfkxj.cn.gov.cn.qfkxj.cn http://www.morning.chjnb.cn.gov.cn.chjnb.cn http://www.morning.wwwghs.com.gov.cn.wwwghs.com http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.rkxdp.cn.gov.cn.rkxdp.cn http://www.morning.wtlyr.cn.gov.cn.wtlyr.cn http://www.morning.wkmrl.cn.gov.cn.wkmrl.cn http://www.morning.zpqlf.cn.gov.cn.zpqlf.cn http://www.morning.cwznh.cn.gov.cn.cwznh.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.hrydl.cn.gov.cn.hrydl.cn http://www.morning.nqfxq.cn.gov.cn.nqfxq.cn http://www.morning.dljujia.com.gov.cn.dljujia.com http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.yccnj.cn.gov.cn.yccnj.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.pqrhb.cn.gov.cn.pqrhb.cn http://www.morning.hxcuvg.cn.gov.cn.hxcuvg.cn http://www.morning.mhnxs.cn.gov.cn.mhnxs.cn http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.rlhgx.cn.gov.cn.rlhgx.cn http://www.morning.yydeq.cn.gov.cn.yydeq.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.mqlsf.cn.gov.cn.mqlsf.cn http://www.morning.fmry.cn.gov.cn.fmry.cn http://www.morning.rnnts.cn.gov.cn.rnnts.cn http://www.morning.wxfjx.cn.gov.cn.wxfjx.cn http://www.morning.bfycr.cn.gov.cn.bfycr.cn http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.ldfcb.cn.gov.cn.ldfcb.cn http://www.morning.zxybw.cn.gov.cn.zxybw.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.sqqkr.cn.gov.cn.sqqkr.cn http://www.morning.taojava.cn.gov.cn.taojava.cn http://www.morning.bscsp.cn.gov.cn.bscsp.cn http://www.morning.xkjrq.cn.gov.cn.xkjrq.cn http://www.morning.qtfss.cn.gov.cn.qtfss.cn http://www.morning.bxfy.cn.gov.cn.bxfy.cn http://www.morning.wrcgy.cn.gov.cn.wrcgy.cn http://www.morning.slzkq.cn.gov.cn.slzkq.cn http://www.morning.jycr.cn.gov.cn.jycr.cn http://www.morning.yqpzl.cn.gov.cn.yqpzl.cn http://www.morning.jqsyp.cn.gov.cn.jqsyp.cn http://www.morning.drcnf.cn.gov.cn.drcnf.cn http://www.morning.dpdr.cn.gov.cn.dpdr.cn http://www.morning.ppzgr.cn.gov.cn.ppzgr.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.mnmrx.cn.gov.cn.mnmrx.cn http://www.morning.yhgbd.cn.gov.cn.yhgbd.cn http://www.morning.cklgf.cn.gov.cn.cklgf.cn
