add: 全排列算法

Eric-art-coder · Eric-art-coder · commit 9cca49fd6fb7 · 2023-10-08T11:40:50.000+08:00
diff --git a/src/arr/readme.md b/src/arr/readme.md
@@ -4,3 +4,19 @@
 
 2、合并有序数组：
 用两个指针，从后往前移动，不断对比加入到新的数组。
+
+3、有一种去深度遍历的方式，很多时候也可以看成是暴力方式，也就是回溯算法，将不符合要求的排除掉。
+```js
+result = []
+function backtrack() {
+  if(满足条件) {
+    resule.push(path)
+    return
+  }
+  for() {
+    // 做选择（前序遍历）
+    backtrack(path, list)
+    // 撤销选择（后续遍历）
+  }
+}
+```
diff --git a/src/arr/全排列.ts b/src/arr/全排列.ts
@@ -0,0 +1,51 @@
+// 给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按照任何顺序返回答案
+// 输入：nums = [1, 2, 3]
+// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
+// 思路：从脑海里要有树的概念，一层层树都是递归去完成，然后通过已经重复来剪去一些小树枝
+function permute(nums) {
+  const res = []
+  backtrack([])
+  return res
+  function backtrack(path) {
+    if(path.length === nums.length) {
+      res.push(path)
+      return
+    }
+    for (let i = 0; i < nums.length; i++) {
+      if(path.includes(nums[i])) { continue; } 
+      backtrack(path.concat(nums[i]))
+    }
+  }
+};
+
+console.log(permute([1,2,3]))
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+// 正确答案
+/**
+const res = []
+backtrack([])
+return res
+function backtrack(path) {
+  if(path.length === nums.length) {
+    res.push(path)
+    return
+  }
+  for (let i = 0; i < nums.length; i++) {
+    if(path.includes(nums[i])) { continue; }
+    backtrack(path.concat(nums[i]))
+  }
+}
+ */
