发表于 更新于 分类于

题目描述

电话号码的字母组合

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

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

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

代码实现

这也是一个典型的回溯算法应用

下面这段代码中使用了 for of 来进行循环，比 for 方便多了，因为 for 还要判断个数。同样，这里的 prefix.pop(); 和 prefix.join('') 需要格外注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {string} digits
 * @return {string[]}
 */
const letters = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz'
};

var letterCombinations = function(digits) {
  let result = [];
  let prefix = [];
  if (digits.length) {
    backTracking(0);
  }

  function backTracking(index) {
    if (index === digits.length) {
      result.push(prefix.join(''));
      return;
    }
    for(let letter of letters[digits[index]]) {
      prefix.push(letter);
      backTracking(index + 1);
      prefix.pop();
    }
  }
  return result;
};

发表于 更新于 分类于

题目描述

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码实现

这是一个典型的回溯算法的应用，在这段代码里 temp.pop() 是点睛之笔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let result = [];

  function backTracking(temp, remain) {
    if (remain.length === 0) {
      result.push(temp.slice());
    }
    for (let i = 0; i < remain.length; i++) {
      temp.push(remain[i]);
      backTracking(temp, [...remain.slice(0, i), ...remain.slice(i + 1)]);
      // backTracking(temp, remain.slice(0, i).concat(remain.slice(i+1)));
      temp.pop();
    }
  }

  backTracking([], nums);
  return result;
};

console.log(permute([1, 2, 3]))
//  [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

发表于 更新于 分类于

题目描述

子集

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

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

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码实现

注意这段代码里的 res.push(temp.slice())，如果没有 slice() 的话，res 的最后子元素会都是空数组，[ [], [], [], [] ]，原因就是我们传递了一个引用类型值 temp，相当于引用的复制，并且在 dfs 函数中我们对 temp 进行了改变，最后 temp 会变成 []。

在下面这段代码里 temp.pop() 是点睛之笔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let result = [];

  function backTracking(temp, index) {
    result.push(temp.slice())
    for (let i = index; i < nums.length; i++) {
      temp.push(nums[i]);
      backTracking(i + 1, temp);
      temp.pop();
    }
  }
  backTracking([], 0);
  return result;
};

下面这段代码中 res.push(temp)，因为我们并没有在 backTracking 函数中改变 temp，而是在参数过程中改变了 temp，其实是利用了 concat。

ES6 …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let result = [];

  function backTracking(temp, index) {
    result.push(temp);
    for (let i = index; i < nums.length; i++) {
      backTracking([...temp, nums[i]], i + 1);
      // backTracking(temp.concat([nums[i]]), i + 1);
    }
  }
  backTracking([], 0);
  return result;
};