[LeetCode] 46. Int数组全排列 ☆☆☆(回溯)
2023-09-14 09:07:35 时间
描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解析
和以前的字符串全排列一样。
官方题解:
回溯法 是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认 不是 一个解的话(或者至少不是 最后一个 解),回溯算法会通过在上一步进行一些变化抛弃该解,即 回溯 并且再次尝试。
这里有一个回溯函数,使用第一个整数的索引作为参数 backtrack(first)。
如果第一个整数有索引 n,意味着当前排列已完成。
遍历索引 first 到索引 n - 1 的所有整数。Iterate over the integers from index first to index n - 1.
在排列中放置第 i 个整数, 即 swap(nums[first], nums[i]).
继续生成从第 i 个整数开始的所有排列: backtrack(first + 1).
现在回溯,即通过 swap(nums[first], nums[i]) 还原.
代码
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); if (nums == null || nums.length <= 0) { return list; } permuteHelp(nums, list, 0); return list; } public void permuteHelp(int[] nums, List<List<Integer>> list, int startIndex) { if (startIndex == nums.length) { List<Integer> tempList = new ArrayList<>(nums.length); for (int num : nums) { tempList.add(num); } list.add(tempList); } for (int i = startIndex; i < nums.length; i++) { swap(nums, i, startIndex); permuteHelp(nums, list, startIndex + 1); swap(nums, i, startIndex); } } public void swap(int[] nums, int left, int right) { if (left == right) { return; } nums[left] = nums[left] ^ nums[right]; nums[right] = nums[left] ^ nums[right]; nums[left] = nums[left] ^ nums[right]; } }
相关文章
- Java实现 LeetCode 715 Range 模块(选范围)
- Java实现 LeetCode 501 二叉搜索树中的众数
- Java实现 LeetCode 81 搜索旋转排序数组 II(二)
- Java实现 LeetCode 55 跳跃游戏
- Java实现 LeetCode 48 旋转图像
- 【数组&双指针】leetcode 234. 回文链表【简单】
- 【数组&双指针】LeetCode 142. 环形链表 II【中等】
- LeetCode(91):解码方法
- [LeetCode] Maximum Gap
- LeetCode(117):填充同一层的兄弟节点 II
- ( “树” 之 BST) 108. 将有序数组转换为二叉搜索树 ——【Leetcode每日一题】
- 【LeetCode 4】寻找两个有序数组的中位数
- 【LeetCode Python实现】153. 寻找旋转排序数组中的最小值(中等)
- Leetcode 2235. 两整数相加
- Leetcode 1603. 设计停车系统
- Leetcode 1979. 找出数组的最大公约数
- Leetcode 1991. 找到数组的中间位置(暴力枚举)
- Leetcode 941. 有效的山脉数组
- [LeetCode] 23. Merge k Sorted Lists ☆☆☆☆☆
- LeetCode Median of Two Sorted Arrays
- 【Leetcode刷题Python】20. 有效的括号
- 【Leetcode刷题Python】295. 数据流的中位数
- 【LeetCode】200. 岛屿数量
- 【LeetCode】剑指 Offer 51. 数组中的逆序对