括号生成、子集和电话号码的字母组合

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

示例

例如，给出 n = 3，生成结果为：
​
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

方法一 回溯法（实现一）

思路

我们知道，有且仅有两种情况，生成的括号序列不合法

• 我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。

• 如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。

基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。

详解

1. 采用回溯法，即把问题的解空间转化成了图或者树的结构表示，然后，使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

2. 如果自定义的字符串长度足够且走到这里，那么就说明这个组合是合适的，我们把它保存。

3. 否则，递归执行添加左括号，添加右括号的操作。

4. 递归结束条件为结果字符串长度等于左右括号的总个数（2n），则返回最终结果。

代码

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = n => {
  const res = [];
  const gen = (str = '', l = 0, r = 0) => {
    // 如果自定义的字符串长度足够且走到这里，那么就说明这个组合是合适的
    if (str.length === 2 * n) {
      res.push(str);
      return;
    }
    // 下面的逻辑：左括号必须出现在右括号的前面
    // 只有在 l >= n 的 时候，才不能添加左括号，其他都可添加
    if (l < n) {
      gen(`${str}(`, l + 1, r);
    }
    // 如果右括号没有左括号多，我们就可以添加一个右括号
    if (r < l) {
      gen(`${str})`, l, r + 1);
    }
  };
  gen();
  return res;
};

复杂度分析

我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析需要更多的背景来解释，但事实证明这是第 n 个卡塔兰数 $\dfrac{1}{n+1}\binom{2n}{n}$，这是由 $\dfrac{4^n}{n\sqrt{n}}$ 渐近界定的。

• 时间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$，在回溯过程中，每个有效序列最多需要 n 步。

• 空间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$，如上所述，并使用 $O(n)$ 的空间来存储序列。

方法二 回溯法（实现二）

思路

整体的实现思路也是回溯法，也是递归来实现该思路，唯一不同的是，递归的结束条件是左右括号都消费尽。

详解

1. 采用回溯法，即把问题的解空间转化成了图或者树的结构表示，然后，使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

2. 首先，先从左括号开始填充。

3. 然后，填充右括号，保证两类括号数目一致，平衡。

4. 递归结束条件为左右括号均消费尽，则输出结果。

代码

/**
 * @param {number} n
 * @return {number}
 */
const generateParenthesis = n => {
  const res = [];
  // left :左括号个数， right:右括号个数
  function helper (left, right, max, str) {
    if (left === max && right === max) {
      res.push(str);
      return;
    }
    // 先从左括号开始填充
    if (left < max) {
      helper(left + 1, right, max, `${str}(`);
    }
    // 保证两类括号数目一致
    if (left > right) {
      helper(left, right + 1, max, `${str})`);
    }
  }
  helper(0, 0, n, '');
  return res;
};

复杂度分析

本方法也是使用回溯法，只是具体实现方式不同，因此，复杂度也是一样的。

• 时间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$​

在回溯过程中，每个有效序列最多需要 $n$ 步。

• 空间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$​

如上所述，并使用 $O(n)$ 的空间来存储序列。

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

方法一 回溯算法

思路

设置初始二维数组[[]]，依次把每个数加入到数组中的每一个元素中，并保留原来的所有元素。

详解

1. 初始化二维数组来存储所有子集；

2. 使用双层遍历，外层遍历 nums 数组，内层遍历二维数组，将每个元素与二维数组每项合并，并保留二维数组原有的元素

3. 并将得到的新子集与二维数组元素合并，最后得到所有子集；

例如：输入 nums = [1, 2, 3] 初始化二维数组存储所有子集 result = [[]] 然后遍历 nums, 1 添加到[], 结果为 [[], [1]]; 2 添加到[], [1], 结果为 [[], [1], [2], [1, 2]]; 3 添加到[], [1], [2], [1, 2], 结果为 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]];

代码

const subsets = (nums) => {
  let result = [[]]; // 初始化二维数组
  for (let i of nums) {
    const temp = [];
    for (let k of result) {
      temp.push(k.concat(i)); // 依次把每个元素添加到数组中
    }
    result = result.concat(temp);
  }
  return result;
}

复杂度分析

• 时间复杂度：$O(2^n)$​

根据上述算法，每次循环 result 数组的次数为 $2^{(n - 1)}$， 则计算总数为 $1 + 2^1 + 2^2 + ... + 2^{(n-1)}$，根据等比数列计算公式得到循环总次数为 $2^n - 1$，所以时间复杂度为 $O(2^n)$。

• 空间复杂度：$O(2^n)$​

根据排列组合原理，子集包含一个数字的情况所耗费的存储空间为 $C_n^1 * 1$ ，包含两个数字所耗费的存储空间为 $C_n^2 * 2$ ，根据算法得出 共需要 $C_n^0 + C_n^1 + 2 * C_n^2 + ... + (n - 1) * C_n^{n - 1} + n * C_n^n$ 个存储空间，根据排列组合公式求和可得需要 $n*2^{n-1} + 1$ 个额外存储空间， 所以算法空间复杂度为 $O(2^n)$。

方法二 二进制表示法

思路

从数学角度看，求子集其实是一个排列组合问题，比如 nums = [1, 2, 3]，存在四种情况：

1. 都不选，情况共有 $C_3^0= 1$种

2. 只选 1 个数，情况共有 $C_3^1 = 3$种

3. 选 2 个数，情况共有 $C_3^2 = 3$ 种

4. 全选，情况共有 $C_3^3 = 1$种

落到数组中的每个数字，都有两种可能，选与不选，我们用 1 标识选，用 0 标识不选。 则 [] 表示为 000，[1, 2, 3] 表示为 111，我们通过转化为二进制表示法，遍历 000 - 111 的所有组合，即可求出所有子集。

详解

1. 根据上述分析，我们得出加入数组为 nums，则针对每位存在选与不选两种情况，那么所有组合数为$2 ^ {length}$ 个。

2. 针对每一种组合情况，我们可以取出该二进制表示法中的每一位，如 110，我们分别通过向右移位并和 1 求与，判断最低为的值为 0 或者 1。

3. 如果得到结果为 1，那么表示该位表示的数字在原数组中被选中，存入暂存数组，一轮遍历后即可获得该组子集的数字组合。将所有子集数字组合一起存入结果数组，即求出所有子集。

代码

const subsets = (nums) => {
  // 子集的数量
  const len = nums.length;
  const setNums = Math.pow(2, len);
  const result = [];
​
  for (let i = 0; i < setNums; i++) {
    let temp = [];
    // 判断该二进制表示法中，每一个位是否存在
    for (let j = 0; j < len; j++) {
      if (1 & (i >> j)) { // 如果该位为 1，则存入组合数组
        temp.push(nums[j]);
      }
    }
​
    result.push(temp);
  }
​
  return result;
};

复杂度分析

• 时间复杂度：$O(2^n)$​

一共包含 $2^n$ 个组合需要 $n * 2^n$ 次计算，所以时间复杂度为 $O(2^n)$。

• 空间复杂度：$O(2^n)$​

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例

输入："23"
​
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
![img](https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/17_telephone_keypad.png)

方法一 挨个遍历

思路

利用队列的先进先出的特点，把队列中的第一个元素拿出，再与后面的挨个拼接

a, b, c --> b, c, ad, ae, af --> c, ad, ae, af, bd, be, bf -> ...

详解

1. 先在队列中插入一个空字符

2. 取出队列中的第一个元素，与后一位数字对应的字符进行挨个拼接

3. 重复第二步，直到结束

代码

const letterCombinations = function (digits) {
  const map = {
    2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z']
  };
​
  if (!digits) {
    return [];
  }
​
  const res = [''];
  for (let i = 0; i < digits.length; i++) {
    const letters = map[digits[i]];
    const size = res.length;
    for (let j = 0; j < size; j++) {
      const temp = res.shift(0); // 取出第一个元素
      for (let k = 0; k < letters.length; k++) {
        res.push(`${temp}${letters[k]}`); // 第一个元素与后一位数字对应的字符进行挨个拼接
      }
    }
  }
  return res;
};

复杂度分析

• 时间复杂度： $O(3^m * 4^n)$

  通过数组的 push 我们发现，循环的次数和最后数组的长度是一样的，然而数组的长度有和输入多个3个字母的数目、4个字母的数目有关，得出时间复杂度为 $O(3^m * 4^n)$

  其中 $m$ 为3个字母的数目，$n$ 为4个字母的数目

• 空间复杂度： $O(3^m * 4^n)$

  最后结果的长度和输入的数字有关，得出复杂度为 $O(3^m * 4^n)$

方法二 回溯

思路

这道题有点排列组合的味道，我们可以穷举所有的可能性，找到所有的可能性

详解

1. 如果还有数字需要被输入，就继续遍历数字对应的字母进行组合 prefix + letter

2. 当发现没有数字输入时，说明已经走完了，得到结果

   代码

const map = {
  2: ['a', 'b', 'c'],
  3: ['d', 'e', 'f'],
  4: ['g', 'h', 'i'],
  5: ['j', 'k', 'l'],
  6: ['m', 'n', 'o'],
  7: ['p', 'q', 'r', 's'],
  8: ['t', 'u', 'v'],
  9: ['w', 'x', 'y', 'z']
};
​
const letterCombinations = function (digits) {
  const result = [];
  function backtrack (prefix, next) {
    // 发现没有字母需要输入时，就可以返回了
    if (next.length === 0) {
      result.push(prefix);
    } else {
      const digit = next[0];
      const letters = map[digit]; // 获取对应的各个字母
      for (let i = 0; i < letters.length; i++) {
        backtrack(prefix + letters[i], next.substr(1));
      }
    }
  }
  if (digits.length !== 0) {
    backtrack('', digits);
  }
  return result;
};

复杂度分析

• 时间复杂度： $O(3^m * 4^n)$

• 空间复杂度： $O(3^m * 4^n)$