46. 全排列

linwt · linwt · commit e2d29ff36713 · 2022-02-13T21:50:58.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -8,6 +8,7 @@
 17. 电话号码的字母组合
 20. 有效的括号
 21. 合并两个有序链表
+46. 全排列
 53. 最大子数组和
 70. 爬楼梯
 94. 二叉树的中序遍历
diff --git a/leetcode_Java/Solution0046.java b/leetcode_Java/Solution0046.java
@@ -0,0 +1,36 @@
+// 全排列
+
+
+/*
+回溯：
+1、定义全局变量res存放回溯过程得到的所有子结果
+2、定义局部变量track存放回溯过程的临时子结果
+3、调用递归函数，处理得到所有子结果，返回结果
+4、定义递归函数
+    1）终止条件，存储子结果
+    2）for循环：剪枝条件 → 做选择 → 递归 → 撤销选择 → 回溯
+ */
+class Solution {
+    private List<List<Integer>> res = new ArrayList<>();
+
+    public List<List<Integer>> permute(int[] nums) {
+        LinkedList<Integer> track = new LinkedList<>();
+        backtrack(nums, track);
+        return res;
+    }
+
+    private void backtrack(int[] nums, LinkedList track) {
+        if (track.size() == nums.length) {
+            res.add(new ArrayList(track));
+            return;
+        }
+        for (int i = 0; i < nums.length; i++) {
+            if (track.contains(nums[i])) {
+                continue;
+            }
+            track.add(nums[i]);
+            backtrack(nums, track);
+            track.removeLast();
+        }
+    }
+}
