一、题目
二、代码
class Solution {int[] nums;List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] onPath;public List<List<Integer>> permute(int[] nums) {this.nums = nums;int n = nums.length;this.onPath = new boolean[n];dfs(0);return ans;}private void dfs(int i) {int n = nums.length;if (i == n) {ans.add(new ArrayList<>(path));return;}for (int j = 0; j < n; j++) {if (!onPath[j]) {// 若未被选中path.add(nums[j]);// 将位置 i 选 nums[j]onPath[j] = true; // 标记为选中dfs(i + 1);onPath[j] = false;// 恢复现场path.remove(i);}}}
}
三、解题思路
通过递归和回溯的方式生成了所有可能的排列。每次递归时,尝试将数组中的每个数字添加到当前的排列路径中,然后继续递归。当达到数组的末尾时,它会将当前的排列路径添加到结果列表中。然后回溯,移除最后一个元素,并尝试下一个可能的数字,直到所有可能的排列都被生成。