商务网站建设工程师,国家拨款农村建设查询的网站,网站建设推广代理公司,浙江嘉兴建设局网站回溯法实现数组全排列的算法 Ⅰ、回溯法实现数组全排列#xff1a;1、题目描述#xff1a;2、解题思路#xff1a;3、实现代码#xff1a; Ⅱ、小结#xff1a; Ⅰ、回溯法实现数组全排列#xff1a;
1、题目描述#xff1a; 给定⼀个 没有重复 数字的序列#xff0c;… 回溯法实现数组全排列的算法 Ⅰ、回溯法实现数组全排列1、题目描述2、解题思路3、实现代码 Ⅱ、小结 Ⅰ、回溯法实现数组全排列
1、题目描述 给定⼀个 没有重复 数字的序列返回其所有可能的全排列。 示例: 输⼊: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 2、解题思路 以 [1,2,3] 为例根据回溯思想我们的逻辑是 先从 [1,2,3] 选取⼀个数。 然后继续从 [1,2,3] 选取⼀个数并且这个数不能是已经选取过的数。 重复这个过程直到选取的数字个数达到了 3。 可能存在的问题
其一、如何确保这个数不能是已经选取过的数
答我们可以直接在已经选取的数字中线性查找也可以将已经选取的数字中放到 hashset 中这样就可以在
O(1)的时间来判断是否已经被选取了只不过需要额外的空间;
3、实现代码
其一、代码为 // 此时的 list 是空数组、tempList 是空数组、nums 是没有重复数字的数组;
const backtrack (list, tempList, nums) {if (tempList.length nums.length) return list.push([...tempList])for (let i 0; i nums.length; i) {// 此时 continue 的作用若 if() 满足条件则会跳出本次的 for 循环;if (tempList.includes(nums[i])) continuetempList.push(nums[i])backtrack(list, tempList, nums)tempList.pop()}
}const permute (nums) {const list []backtrack(list, [], nums)return list
}// 此时的输出结果为[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ];
permute([1, 2, 3])
执行 backtrack(list, [], nums) 函数后代码执行的过程(即执行 backtrack([], [], [1,2,3]) 函数)注意里面涉及多个循环嵌套递归每次递归的出口为 tempList.length nums.length循环的出口为 for() 循环结束;第一层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后tempList 数组为 [1];backtrack(list, tempList, nums) 执行代码为backtrack([], [1], [1,2,3])第二层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第二层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后tempList 数组为 [1,2];backtrack(list, tempList, nums) 执行代码为backtrack([], [1,2], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后tempList 数组为 [1,2,3];backtrack(list, tempList, nums) 执行代码为backtrack([], [1,2,3], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3]];执行 tempList.pop() 代码后tempList 数组为 [1,2];执行 tempList.pop() 代码后tempList 数组为 [1];第二层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后tempList 数组为 [1,3];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3]], [1,3], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后tempList 数组为 [1,3,2];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3]], [1,3,2], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3],[1,3,2]];执行 tempList.pop() 代码后tempList 数组为 [1,3];第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程; 执行 tempList.pop() 代码后tempList 数组为 [1];执行 tempList.pop() 代码后tempList 数组为 [];第一层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后tempList 数组为 [2];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2]], [2], [1,2,3])第二层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后tempList 数组为 [2,1];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2]], [2,1], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后tempList 数组为 [2,1,3];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2]], [2,1,3], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3],[1,3,2],[2,1,3]];执行 tempList.pop() 代码后tempList 数组为 [2,1];执行 tempList.pop() 代码后tempList 数组为 [2];第二层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第二层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后tempList 数组为 [2,3];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3]], [2,3], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后tempList 数组为 [2,3,1];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3]], [2,3,1], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1]];执行 tempList.pop() 代码后tempList 数组为 [2,3];第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程; 执行 tempList.pop() 代码后tempList 数组为 [2];执行 tempList.pop() 代码后tempList 数组为 [];第一层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后tempList 数组为 [3];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3], [1,2,3])第二层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后tempList 数组为 [3,1];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3,1], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后tempList 数组为 [3,1,2];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3,1,2], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]];执行 tempList.pop() 代码后tempList 数组为 [3,1];第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;执行 tempList.pop() 代码后tempList 数组为 [3];第二层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后tempList 数组为 [3,2];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]], [3,2], [1,2,3])第三层循环在 i0 的情况下if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后tempList 数组为 [3,2,1];backtrack(list, tempList, nums) 执行代码为backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]], [3,2,1], [1,2,3])if (tempList.length nums.length) return list.push([...tempList])list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];执行 tempList.pop() 代码后tempList 数组为 [3,2];第三层循环在 i1 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;第三层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程; 执行 tempList.pop() 代码后tempList 数组为 [3];第二层循环在 i2 的情况下if (tempList.includes(nums[i])) continue 的判断成功因此直接跳出此次的 for() 循环的过程;执行 tempList.pop() 代码后tempList 数组为 [];因此最后 list 的输出结果为[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ],
而 tempList 的输出结果为[];
其二、截图为 Ⅱ、小结
其一、哪里有不对或不合适的地方还请大佬们多多指点和交流 其二、若有转发或引用本文章内容请注明本博客地址(直接点击下面 url 跳转) https://blog.csdn.net/weixin_43405300,创作不易且行且珍惜 其三、有兴趣的话可以多多关注这个专栏(Vue(Vue2Vue3)面试必备专栏)(直接点击下面 url 跳转)https://blog.csdn.net/weixin_43405300/category_11525646.html?spm1001.2014.3001.5482
