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

括号生成

给出 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 个卡塔兰数 1n+1(2nn)\dfrac{1}{n+1}\binom{2n}{n},这是由 4nnn\dfrac{4^n}{n\sqrt{n}} 渐近界定的。

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

  • 空间复杂度:O(4nn)O(\dfrac{4^n}{\sqrt{n}}),如上所述,并使用 O(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(4nn)O(\dfrac{4^n}{\sqrt{n}})

在回溯过程中,每个有效序列最多需要 nn 步。

  • 空间复杂度:O(4nn)O(\dfrac{4^n}{\sqrt{n}})

如上所述,并使用 O(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(2n)O(2^n)

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

  • 空间复杂度:O(2n)O(2^n)

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

方法二 二进制表示法

思路

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

  1. 都不选,情况共有 C30=1C_3^0= 1

  2. 只选 1 个数,情况共有 C31=3C_3^1 = 3

  3. 选 2 个数,情况共有 C32=3C_3^2 = 3

  4. 全选,情况共有 C33=1C_3^3 = 1

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

详解

  1. 根据上述分析,我们得出加入数组为 nums,则针对每位存在选与不选两种情况,那么所有组合数为2length 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(2n)O(2^n)

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

  • 空间复杂度:O(2n)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(3m4n)O(3^m * 4^n)

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

    其中 mm 为3个字母的数目,nn 为4个字母的数目

  • 空间复杂度: O(3m4n)O(3^m * 4^n)

    最后结果的长度和输入的数字有关,得出复杂度为 O(3m4n)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(3m4n)O(3^m * 4^n)

  • 空间复杂度: O(3m4n)O(3^m * 4^n)