力扣46.全排列
一、题目
二、代码
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);
}
}
}
}
三、解题思路
通过递归和回溯的方式生成了所有可能的排列。每次递归时,尝试将数组中的每个数字添加到当前的排列路径中,然后继续递归。当达到数组的末尾时,它会将当前的排列路径添加到结果列表中。然后回溯,移除最后一个元素,并尝试下一个可能的数字,直到所有可能的排列都被生成。
原文地址:https://blog.csdn.net/J_pluto/article/details/142370211
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!