求解思路
从左到右按照位置顺序逐个固定每个位置上的元素,对于当前位置 i,通过交换操作依次尝试将后续区间 [i, n-1] 中的每个元素放到位置 i,然后递归地处理位置 i+1 及其后续位置,当所有位置都确定后就得到一个完整的排列,而每次递归返回后通过再次交换恢复数组到进入递归前的状态,这样就能继续尝试为当前位置选择其他元素。
完整代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public class Solution {
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
f(nums, 0, ans);
return ans;
}
public static void f(int[] nums, int i, List<List<Integer>> ans) {
// 递归终止条件:所有位置都已固定
if (i == nums.length) {
List<Integer> cur = new ArrayList<>();
for (int num : nums) {
cur.add(num);
}
ans.add(cur);
} else {
// 尝试将 [i, n-1] 范围内的每个元素放到位置 i
for (int j = i; j < nums.length; j++) {
swap(nums, i, j); // 选择:将 nums[j] 放到位置 i
f(nums, i + 1, ans); // 递归:处理后续位置
swap(nums, i, j); // 回溯:恢复原状,尝试其他选择
}
}
}
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~