95% 的算法都是基于这 6 种算法思想

原始问题可以分成多个相似的子问题子问题可以很简单的求解原始问题的解是子问题解的合并各个子问题是相互独立的，不包含相同的子问题

第一步：分解，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题第二步：解决，解决各个子问题第三步：合并，将各个子问题的解合并为原问题的解

二分查找归并排序快速排序汉诺塔问题React 时间分片

选择数组中的中间数

比中间数低，则去中间数左边的子数组中寻找；比中间数高，则去中间数右边的子数组中寻找；相等则返回查找成功

原问题复杂度过高求全局最优解的数学模型难以建立或计算量过大没有太大必要一定要求出全局最优解，“比较优”就可以

首先，我们需要明确什么是最优解（期望）然后，把问题分成多个步骤，每一步都需要满足：

可行性：每一步都满足问题的约束



局部最优：每一步都做出一个局部最优的选择

- 不可取消：选择一旦做出，在后面遇到任何情况都不可取消最后，叠加所有步骤的最优解，就是全局最优解

最小生成树算法单源最短路径的 Dijkstra 算法Huffman 压缩编码背包问题活动选择问题等

首先 a1 活动的结束时间最早，选择 a1 活动a1 结束后，a2 有时间冲突，不可选择，a3、a4 都可选择，但 a4 结束时间最早，选择 a4依次选择时间没有冲突的，又结束时间最早的活动

深度优先搜索0-1背包问题正则表达式匹配八皇后数独全排列

var string = "abbc"
var regex = /ab{1,3}c/
console.log( string.match(regex) )
// ["abbc", index: 0, input: "abbc", groups: undefined]

定义子问题实现需要反复执行解决的子子问题部分识别并求解出边界条件

爬楼梯问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？背包问题：给出一些资源（有总量及价值），给一个背包（有总容量），往背包里装资源，目标是在背包不超过总容量的情况下，装入更多的价值硬币找零：给出面额不定的一定数量的零钱，以及需要找零的钱数，找出有多少种找零方案图的全源最短路径：一个图中包含 u、v 顶点，找出从顶点 u 到顶点 v 的最短路径最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变剩下元素的顺序实现）

= dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(n)

优化空间复杂度：
let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}
空间复杂度：O(1)
6 枚举算法

6.1 算法策略

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。
6.2 解题思路

确定枚举对象、枚举范围和判定条件。逐一列举可能的解，验证每个解是否是问题的解。

7 刷题

7.1 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意： 给定 n 是一个正整数。</p>示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解法：动态规划

动态规划（Dynamic Programming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

定义子问题实现需要反复执行解决的子子问题部分识别并求解出边界条件

第一步：定义子问题
如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数
第二步：实现需要反复执行解决的子子问题部分
dp[n] = dp[n1] + dp[n2]
第三步：识别并求解出边界条件
// 第 0 级 1 种方案
dp[0]=1
// 第 1 级也是 1 种方案
dp[1]=1
最后一步：把尾码翻译成代码，处理一些边界情况
let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(n)

优化空间复杂度：
let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}
空间复杂度：O(1)
更多解答
7.2 使用最小花费爬楼梯

数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost (索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：

cost 的长度将会在 [2, 1000] 。每一个 cost 将会是一个Integer类型，范围为 [0, 999] 。

解法：动态规划

本题注意理解题意：

第 i 级台阶是第 i-1 级台阶的阶梯顶部。踏上第 i 级台阶花费 cost ，直接迈一大步跨过而不踏上去则不用花费。楼梯顶部在数组之外，如果数组长度为 len，那么楼顶就在下标为 len

第一步：定义子问题
踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost最后迈 1 步踏上第 i 级台阶：dp[i-2] + cost

第二步：实现需要反复执行解决的子子问题部分
所以踏上第 i 级台阶的最小花费为：
dp = min(dp[i-2], dp[i-1]) + cost
第三步：识别并求解出边界条件
// 第 0 级 cost[0] 种方案
dp[0] = cost[0]
// 第 1 级，有两种情况
// 1：分别踏上第0级与第1级台阶，花费cost[0] + cost[1]
// 2：直接从地面开始迈两步直接踏上第1级台阶，花费cost[1]
dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]
最后一步：把尾码翻译成代码，处理一些边界情况
let minCostClimbingStairs = function(cost) {
    cost.push(0)
    let dp = [], n = cost.length
    dp[0] = cost[0]
    dp[1] = cost[1]
    for(let i = 2; i < n; i++){
        dp = Math.min(dp[i-2] , dp[i-1]) + cost
    }
    return dp[n-1]
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(n)

优化：
let minCostClimbingStairs = function(cost) {
    let n = cost.length,
        n1 = cost[0],
        n2 = cost[1]
    for(let i = 2;i < n;i++){
        let tmp = n2
        n2 = Math.min(n1,n2)+cost
        n1 = tmp
    }
    return Math.min(n1,n2)
};

时间复杂度：O(n)空间复杂度：O(1)

更多解答
7.3 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
第一步：定义子问题
动态规划是将整个数组归纳考虑，假设我们已经知道了以第 i-1 个数结尾的连续子数组的最大和 dp[i-1]，显然以第i个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums，要么就是 nums 单独成一组，也就是 nums ，在这两个数中我们取最大值
第二步：实现需要反复执行解决的子子问题部分
dp[n] = Math.max(dp[n1]+nums[n], nums[n])
第三步：识别并求解出边界条件
dp[0]=nums[0]
最后一步：把尾码翻译成代码，处理一些边界情况
因为我们在计算 dp 的时候，只关心 dp[i-1] 与 nums，因此不用把整个 dp 数组保存下来，只需设置一个 pre 保存 dp[i-1] 就好了。
代码实现（优化）：
let maxSubArray = function(nums) {
    let max = nums[0], pre = 0
    for(const num of nums) {
        if(pre > 0) {
            pre += num
        } else {
            pre = num
        }
        max = Math.max(max, pre)
    }
    return max
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(1)

更多解答
7.4 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解法：动态规划

第一步：定义子问题
动态规划是将整个数组归纳考虑，假设我们已经知道了 i-1 个股票的最大利润为 dp[i-1]，显然 i 个连续股票的最大利润为 dp[i-1] ，要么就是就是 prices - minprice （ minprice 为前 i-1 支股票的最小值 ），在这两个数中我们取最大值
第二步：实现需要反复执行解决的子子问题部分
dp = Math.max(dp[i1], prices - minprice)
第三步：识别并求解出边界条件
dp[0]=0
最后一步：把尾码翻译成代码，处理一些边界情况
因为我们在计算 dp 的时候，只关心 dp[i-1] 与 prices，因此不用把整个 dp 数组保存下来，只需设置一个 max 保存 dp[i-1] 就好了。
代码实现（优化）：
let maxProfit = function(prices) {
    let max = 0, minprice = prices[0]
    for(let i = 1; i < prices.length; i++) {
        minprice = Math.min(prices, minprice)
        max = Math.max(max, prices - minprice)
    }
    return max
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(1)

更多解答
7.5 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

输入的字符串长度不会超过 1000 。

解法一：暴力法

let countSubstrings = function(s) {
  let count = 0
for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPalindrome(s.substring(i, j + 1))) {
        count++
      }
    }
  }
  return count
}

let isPalindrome = function(s) {
  let i = 0, j = s.length - 1
  while (i < j) {
    if (s != s[j]) return false
    i++
    j--
  }
  return true
}
复杂度分析：

时间复杂度：O(n^3^)空间复杂度：O(1)

解法二：动态规划

一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。
我们怎么去描述子问题呢？
显然，一个子串由两端的 i 、j 指针确定，就是描述子问题的变量，子串 s[i...j] （ dp[j] ） 是否是回文串，就是子问题。
我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。
    j
    a  a  b  a
i a
  a      
  b      
  a         
注意： i<=j ，只需用半张表，竖向扫描
所以：
i === j：dp[j]=true
j - i == 1 && s == s[j]：dp[j] = true
j - i > 1 && s == s[j] && dp[i + 1][j - 1]：dp[j] = true
即：
s == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[j]=true
否则为 false
代码实现：
let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)

  for (let i = 0; i < len; i++) {
    dp = new Array(len).fill(false)
  }
  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
        dp[j] = true
        count++
      } else {
        dp[j] = false
      }
    }
  }
  return count
}
代码实现（优化）：
把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将 dp 定义为一维数组即可
let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)

  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s === s[j] && (j - i <= 1 || dp[i + 1])) {
        dp = true
        count++
      } else {
        dp = false
      }
    }
  }
  return count;
}
复杂度分析：

时间复杂度：O(n^2^)空间复杂度：O(n)

更多解答
7.6 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

解法：动态规划

第 1 步：定义状态
dp[j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s 和 s[j] 。
第 2 步：思考状态转移方程
对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串
dp[j] = (s === s[j]) && dp[i+1][j-1]
第 3 步：初始状态：
dp = true // 单个字符是回文串
if(s === s[i+1]) dp[i+1] = true // 连续两个相同字符是回文串
代码实现：
const longestPalindrome = (s) => {
  if (s.length < 2) return s
  // res: 最长回文子串
  let res = s[0], dp = []
  for (let i = 0; i < s.length; i++) {
    dp = true
  }
  for (let j = 1; j < s.length; j++) {
    for (let i = 0; i < j; i++) {
      if (j - i === 1 && s === s[j]) {
        dp[j] = true
      } else if (s === s[j] && dp[i + 1][j - 1]) {
        dp[j] = true
      }   
      // 获取当前最长回文子串
      if (dp[j] && j - i + 1 > res.length) {
        res = s.substring(i, j + 1)
      }
    }
  }

  return res
}
复杂度分析：

时间复杂度：O(n^2^)空间复杂度：O(n^2^)

更多解答
7.7 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。



示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.lengthn == grid.length1 <= m, n <= 2000 <= grid[j] <= 100

1、DP方程 当前项最小路径和 = 当前项值 + 上项或左项中的最小值 grid[j] += Math.min( grid[i - 1][j], grid[j - 1] )
2、边界处理 grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和 计算第一行：
for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]
计算第一列：
for(let i = 1; i < row; i++) grid[0] += grid[i - 1][0]
3、代码实现
var minPathSum = function(grid) {
    let row = grid.length, col = grid[0].length

    // calc boundary
    for(let i = 1; i < row; i++)
        // calc first col
        grid[0] += grid[i - 1][0]

    for(let j = 1; j < col; j++)
        // calc first row
        grid[0][j] += grid[0][j - 1]

    for(let i = 1; i < row; i++)
        for(let j = 1; j < col; j++)
            grid[j] += Math.min(grid[i - 1][j], grid[j - 1])
   
    return grid[row - 1][col - 1]
};
更多解答
7.8 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：

1 <= prices.length <= 3 * 10 ^ 40 <= prices <= 10 ^ 4

解法一：峰底买入，峰顶卖出



如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下
解法二：贪心算法

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。
某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。
对应于该题，第一天买入，第二天卖出，…，第 i 天买入，第 i+1 天卖出，如果 i 天买入第 i+1 天卖出有利润则买入，否则不买
第 i-1 天买入第 i 天卖出获利 prices[i+1]-prices ，我们仅仅需要将 prices[i+1]-prices 的所有正值加起来就是可获取的最大利益
代码实现：
let maxProfit = function(prices) {
    let profit = 0
    for (let i = 0; i < prices.length - 1; i++) {
        if (prices[i + 1] > prices) {
            profit += prices[i + 1] - prices
        }
    }
    return profit
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(1)

更多解答
7.9 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 g~i~ ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s~j~。如果 s~j~ >= g~i~ ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:
输入: [1,2], [1,2,3]

输出: 2

解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

解法：贪心算法

const findContentChildren = (g, s) => {
    if (!g.length || !s.length) return 0
   
    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)
   
    let gi = 0, si = 0
    while (gi < g.length && si < s.length) {
        if (g[gi] <= s[si++]) gi++
    }
    return gi
}
更多解答
7.10 分割数组为连续子序列

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。
如果可以完成上述分割，则返回 true ；否则，返回 false 。
示例 1：
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

示例 2：
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5

示例 3：
输入: [1,2,3,4,4,5]
输出: False

提示：

输入的数组长度范围为 [1, 10000]

解法：贪心算法

从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为3），剔除之后，依次往后遍历：

判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接如果不可以，则判断以当前元素开始能否构成连续子序列（长度为3），可以的话，则剔除连续子序列否则，返回 false

const isPossible = function(nums) {
    let max = nums[nums.length - 1]
    // arr：存储原数组中数字每个数字出现的次数
    // tail：存储以数字num结尾的且符合题意的连续子序列个数
    let arr = new Array(max + 2).fill(0),
        tail = new Array(max + 2).fill(0)
    for(let num of nums) {
        arr[num] ++
    }
    for(let num of nums) {
        if(arr[num] === 0) continue
        else if(tail[num-1] > 0){
            tail[num-1]--
            tail[num]++
        }else if(arr[num+1] > 0 && arr[num+2] > 0){
            arr[num+1]--
            arr[num+2]--
            tail[num+2]++
        } else {
            return false
        }
        arr[num]--
    }
    return true
}
复杂度分析：

时间复杂度：O(n)空间复杂度：O(n)

更多解答
7.11 全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
解法：回溯算法

本题是回溯算法的经典应用场景
1. 算法策略
回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。
2. 适用场景
回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。
3. 代码实现
我们可以写一下，数组 [1, 2, 3] 的全排列有：

先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
这显然是一个 递归 结构；

递归的终止条件是：一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

let permute = function(nums) {
    // 使用一个数组保存所有可能的全排列
    let res = []
    if (nums.length === 0) {
        return res
    }
    let used = {}, path = []
    dfs(nums, nums.length, 0, path, used, res)
    return res
}
let dfs = function(nums, len, depth, path, used, res) {
    // 所有数都填完了
    if (depth === len) {
        res.push([...path])
        return
    }
    for (let i = 0; i < len; i++) {
        if (!used) {
            // 动态维护数组
            path.push(nums)
            used = true
            // 继续递归填下一个数
            dfs(nums, len, depth + 1, path, used, res)
            // 撤销操作
            used = false
            path.pop()
        }
      
    }
}
4. 复杂度分析

时间复杂度：O(nn!)，其中 n 为序列的长度
这是一个排列组合，每层的排列组合数为：A^m^ ~n~=n!/(nm)! ，故而所有的排列有 ：
A^1^ ~n~ + A^2^ ~n~ + … + A^n-1^ ~n~ = n!/(n1)! + n!/(n2)! + … + n! = n! * (1/(n1)! + 1/(n2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1^) < 2 * n!
并且每个内部结点循环 n 次，故非叶子结点的时间复杂度为 O(nn!)空间复杂度：O(n)

更多解答
7.12 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
解答：回溯算法（深度优先遍历）

算法策略： 回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。
对应于本题，我们可以每次试探增加 ( 或 ) ，注意：

加入 ( 的条件是，当前是否还有 ( 可以选择加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

代码实现：
const generateParenthesis = (n) => {
    const res = []
    const dfs = (path, left, right) => {
        // 肯定不合法，提前结束
        if (left > n || left < right) return
        // 到达结束条件
        if (left + right === 2 * n) {
            res.push(path)
            return
        }
        // 选择
        dfs(path + '(', left + 1, right)
        dfs(path + ')', left, right + 1)
    }
    dfs('', 0, 0)
    return res
}
复杂度分析（来源leetcode官方题解）：


好啦，以上呢就是今天的内容，如果对大家有帮助的话，建议收藏，或者大家有什么更好的学习方法也可以交流互相学习哦！