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

括号生成
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
示例
1
例如，给出 n = 3，生成结果为：
2
​
3
[
4
  "((()))",
5
  "(()())",
6
  "(())()",
7
  "()(())",
8
  "()()()"
9
]
Copied!
方法一 回溯法（实现一）
思路
我们知道，有且仅有两种情况，生成的括号序列不合法
我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。
如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。
基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。
详解
1.采用回溯法，即把问题的解空间转化成了图或者树的结构表示，然后，使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
2.如果自定义的字符串长度足够且走到这里，那么就说明这个组合是合适的，我们把它保存。
3.否则，递归执行添加左括号，添加右括号的操作。
4.递归结束条件为结果字符串长度等于左右括号的总个数（2n），则返回最终结果。
代码
1
/**
2
 * @param {number} n
3
 * @return {string[]}
4
 */
5
const generateParenthesis = n => {
6
  const res = [];
7
  const gen = (str = '', l = 0, r = 0) => {
8
    // 如果自定义的字符串长度足够且走到这里，那么就说明这个组合是合适的
9
    if (str.length === 2 * n) {
10
      res.push(str);
11
      return;
12
    }
13
    // 下面的逻辑：左括号必须出现在右括号的前面
14
    // 只有在 l >= n 的 时候，才不能添加左括号，其他都可添加
15
    if (l < n) {
16
      gen(`${str}(`, l + 1, r);
17
    }
18
    // 如果右括号没有左括号多，我们就可以添加一个右括号
19
    if (r < l) {
20
      gen(`${str})`, l, r + 1);
21
    }
22
  };
23
  gen();
24
  return res;
25
};
Copied!
复杂度分析
我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析需要更多的背景来解释，但事实证明这是第 n 个卡塔兰数 1n+1(2nn)\dfrac{1}{n+1}\binom{2n}{n}n+11​(n2n​)
，这是由 4nnn\dfrac{4^n}{n\sqrt{n}} nn​4n​
 渐近界定的。
时间复杂度：O(4nn)O(\dfrac{4^n}{\sqrt{n}})O(n​4n​)
，在回溯过程中，每个有效序列最多需要 n 步。
空间复杂度：O(4nn)O(\dfrac{4^n}{\sqrt{n}})O(n​4n​)
，如上所述，并使用 O(n)O(n)O(n)
 的空间来存储序列。
方法二 回溯法（实现二）
思路
整体的实现思路也是回溯法，也是递归来实现该思路，唯一不同的是，递归的结束条件是左右括号都消费尽。
详解
1.采用回溯法，即把问题的解空间转化成了图或者树的结构表示，然后，使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
2.首先，先从左括号开始填充。
3.然后，填充右括号，保证两类括号数目一致，平衡。
4.递归结束条件为左右括号均消费尽，则输出结果。
代码
1
/**
2
 * @param {number} n
3
 * @return {number}
4
 */
5
const generateParenthesis = n => {
6
  const res = [];
7
  // left :左括号个数， right:右括号个数
8
  function helper (left, right, max, str) {
9
    if (left === max && right === max) {
10
      res.push(str);
11
      return;
12
    }
13
    // 先从左括号开始填充
14
    if (left < max) {
15
      helper(left + 1, right, max, `${str}(`);
16
    }
17
    // 保证两类括号数目一致
18
    if (left > right) {
19
      helper(left, right + 1, max, `${str})`);
20
    }
21
  }
22
  helper(0, 0, n, '');
23
  return res;
24
};
Copied!
复杂度分析
本方法也是使用回溯法，只是具体实现方式不同，因此，复杂度也是一样的。
时间复杂度：O(4nn)O(\dfrac{4^n}{\sqrt{n}})O(n​4n​)
​
在回溯过程中，每个有效序列最多需要 nnn
 步。
空间复杂度：O(4nn)O(\dfrac{4^n}{\sqrt{n}})O(n​4n​)
​
如上所述，并使用 O(n)O(n)O(n)
 的空间来存储序列。
子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例
1
输入: nums = [1,2,3]
2
输出:
3
[
4
  [3],
5
  [1],
6
  [2],
7
  [1,2,3],
8
  [1,3],
9
  [2,3],
10
  [1,2],
11
  []
12
]
Copied!
方法一 回溯算法
思路
设置初始二维数组[[]]，依次把每个数加入到数组中的每一个元素中，并保留原来的所有元素。
详解
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]];
代码
1
const subsets = (nums) => {
2
  let result = [[]]; // 初始化二维数组
3
  for (let i of nums) {
4
    const temp = [];
5
    for (let k of result) {
6
      temp.push(k.concat(i)); // 依次把每个元素添加到数组中
7
    }
8
    result = result.concat(temp);
9
  }
10
  return result;
11
}
Copied!
复杂度分析
时间复杂度：O(2n)O(2^n)O(2n)
​
根据上述算法，每次循环 result 数组的次数为 2(n−1)2^{(n - 1)}2(n−1)
， 则计算总数为 1+21+22+...+2(n−1)1 + 2^1 + 2^2 + ... + 2^{(n-1)}1+21+22+...+2(n−1)
，根据等比数列计算公式得到循环总次数为 2n−12^n - 12n−1
，所以时间复杂度为 O(2n)O(2^n)O(2n)
。
空间复杂度：O(2n)O(2^n)O(2n)
​
根据排列组合原理，子集包含一个数字的情况所耗费的存储空间为 Cn1∗1C_n^1 * 1Cn1​∗1
 ，包含两个数字所耗费的存储空间为 Cn2∗2C_n^2 * 2Cn2​∗2
 ，根据算法得出 共需要 Cn0+Cn1+2∗Cn2+...+(n−1)∗Cnn−1+n∗CnnC_n^0 + C_n^1 + 2 * C_n^2 + ... + (n - 1) * C_n^{n - 1} + n * C_n^nCn0​+Cn1​+2∗Cn2​+...+(n−1)∗Cnn−1​+n∗Cnn​
 个存储空间，根据排列组合公式求和可得需要 n∗2n−1+1n*2^{n-1} + 1n∗2n−1+1
 个额外存储空间， 所以算法空间复杂度为 O(2n)O(2^n)O(2n)
。
方法二 二进制表示法
思路
从数学角度看，求子集其实是一个排列组合问题，比如 nums = [1, 2, 3]，存在四种情况：
1.都不选，情况共有 C30=1C_3^0= 1C30​=1
种
2.只选 1 个数，情况共有 C31=3C_3^1 = 3C31​=3
种
3.选 2 个数，情况共有 C32=3C_3^2 = 3C32​=3
 种
4.全选，情况共有 C33=1C_3^3 = 1C33​=1
种
落到数组中的每个数字，都有两种可能，选与不选，我们用 1 标识选，用 0 标识不选。 则 [] 表示为 000，[1, 2, 3] 表示为 111，我们通过转化为二进制表示法，遍历 000 - 111 的所有组合，即可求出所有子集。
详解
1.根据上述分析，我们得出加入数组为 nums，则针对每位存在选与不选两种情况，那么所有组合数为2length 2 ^ {length}2length
 个。
2.针对每一种组合情况，我们可以取出该二进制表示法中的每一位，如 110，我们分别通过向右移位并和 1 求与，判断最低为的值为 0 或者 1。
3.如果得到结果为 1，那么表示该位表示的数字在原数组中被选中，存入暂存数组，一轮遍历后即可获得该组子集的数字组合。将所有子集数字组合一起存入结果数组，即求出所有子集。
代码
1
const subsets = (nums) => {
2
  // 子集的数量
3
  const len = nums.length;
4
  const setNums = Math.pow(2, len);
5
  const result = [];
6
​
7
  for (let i = 0; i < setNums; i++) {
8
    let temp = [];
9
    // 判断该二进制表示法中，每一个位是否存在
10
    for (let j = 0; j < len; j++) {
11
      if (1 & (i >> j)) { // 如果该位为 1，则存入组合数组
12
        temp.push(nums[j]);
13
      }
14
    }
15
​
16
    result.push(temp);
17
  }
18
​
19
  return result;
20
};
Copied!
复杂度分析
时间复杂度：O(2n)O(2^n)O(2n)
​
一共包含 2n2^n2n
 个组合需要 n∗2nn * 2^nn∗2n
 次计算，所以时间复杂度为 O(2n)O(2^n)O(2n)
。
空间复杂度：O(2n)O(2^n)O(2n)
​
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例
1
输入："23"
2
​
3
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
4
![img](https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/17_telephone_keypad.png)
Copied!
方法一 挨个遍历
思路
利用队列的先进先出的特点，把队列中的第一个元素拿出，再与后面的挨个拼接
a, b, c --> b, c, ad, ae, af --> c, ad, ae, af, bd, be, bf -> ...
详解
1.先在队列中插入一个空字符
2.取出队列中的第一个元素，与后一位数字对应的字符进行挨个拼接
3.重复第二步，直到结束
代码
1
const letterCombinations = function (digits) {
2
  const map = {
3
    2: ['a', 'b', 'c'],
4
    3: ['d', 'e', 'f'],
5
    4: ['g', 'h', 'i'],
6
    5: ['j', 'k', 'l'],
7
    6: ['m', 'n', 'o'],
8
    7: ['p', 'q', 'r', 's'],
9
    8: ['t', 'u', 'v'],
10
    9: ['w', 'x', 'y', 'z']
11
  };
12
​
13
  if (!digits) {
14
    return [];
15
  }
16
​
17
  const res = [''];
18
  for (let i = 0; i < digits.length; i++) {
19
    const letters = map[digits[i]];
20
    const size = res.length;
21
    for (let j = 0; j < size; j++) {
22
      const temp = res.shift(0); // 取出第一个元素
23
      for (let k = 0; k < letters.length; k++) {
24
        res.push(`${temp}${letters[k]}`); // 第一个元素与后一位数字对应的字符进行挨个拼接
25
      }
26
    }
27
  }
28
  return res;
29
};
Copied!
复杂度分析
时间复杂度： O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 
通过数组的 push 我们发现，循环的次数和最后数组的长度是一样的，然而数组的长度有和输入多个3个字母的数目、4个字母的数目有关，得出时间复杂度为 O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 
其中 mmm
 为3个字母的数目，nnn
 为4个字母的数目
空间复杂度： O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 
最后结果的长度和输入的数字有关，得出复杂度为 O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 
方法二 回溯
思路
这道题有点排列组合的味道，我们可以穷举所有的可能性，找到所有的可能性
详解
1.如果还有数字需要被输入，就继续遍历数字对应的字母进行组合 prefix + letter
2.当发现没有数字输入时，说明已经走完了，得到结果
代码
1
const map = {
2
  2: ['a', 'b', 'c'],
3
  3: ['d', 'e', 'f'],
4
  4: ['g', 'h', 'i'],
5
  5: ['j', 'k', 'l'],
6
  6: ['m', 'n', 'o'],
7
  7: ['p', 'q', 'r', 's'],
8
  8: ['t', 'u', 'v'],
9
  9: ['w', 'x', 'y', 'z']
10
};
11
​
12
const letterCombinations = function (digits) {
13
  const result = [];
14
  function backtrack (prefix, next) {
15
    // 发现没有字母需要输入时，就可以返回了
16
    if (next.length === 0) {
17
      result.push(prefix);
18
    } else {
19
      const digit = next[0];
20
      const letters = map[digit]; // 获取对应的各个字母
21
      for (let i = 0; i < letters.length; i++) {
22
        backtrack(prefix + letters[i], next.substr(1));
23
      }
24
    }
25
  }
26
  if (digits.length !== 0) {
27
    backtrack('', digits);
28
  }
29
  return result;
30
};
Copied!
复杂度分析
时间复杂度： O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 
空间复杂度： O(3m∗4n)O(3^m * 4^n)O(3m∗4n)
 