77. 组合

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

  1. 示例 1:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    输入:n = 4, k = 2
    输出:
    [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
    ]
  2. 示例 2:

    1
    2
    输入:n = 1, k = 1
    输出:[[1]]
  • 提示:

    1
    2
    1 <= n <= 20
    1 <= k <= n

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 思路:回溯/递归 + 剪枝
var combine = function(n, k) {
const ans = [];
const dfs = (cur, n, k, temp) => {
// 剪枝:temp 长度加上区间 [cur, n] 的长度小于 k,不可能构造出长度为 k 的 temp
if (temp.length + (n - cur + 1) < k) {
return;
}
// 记录合法的答案
if (temp.length == k) {
ans.push(temp);
return;
}
// 考虑选择当前位置
dfs(cur + 1, n, k, [...temp, cur]);
// 考虑不选择当前位置
dfs(cur + 1, n, k, temp);
}
dfs(1, n, k, []);
return ans;
};

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  1. 示例 1:

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

    1
    2
    输入:nums = [0,1]
    输出:[[0,1],[1,0]]
  3. 示例 3:

    1
    2
    输入:nums = [1]
    输出:[[1]]
  • 提示:

    1
    2
    3
    1 <= nums.length <= 6
    -10 <= nums[i] <= 10
    nums 中的所有整数 互不相同

题 解

1
2
3
4
5
6
7
8
9
10
11
12
# 思路:回溯
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(nums, tmp):
if not nums:
res.append(tmp)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
backtrack(nums, [])
return res

784. 字母大小写全排列

给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

  • 示例:

    1
    2
    输入:S = "a1b2"
    输出:["a1b2", "a1B2", "A1b2", "A1B2"]
    1
    2
    输入:S = "3z4"
    输出:["3z4", "3Z4"]
    1
    2
    输入:S = "12345"
    输出:["12345"]
  • 提示:

    1. S 的长度不超过12。
    2. S 仅由数字和字母组成。

题 解

1
2
3
4
5
# 思路:内置函数库(这算是捡漏? 反正通过了)
class Solution(object):
def letterCasePermutation(self, S):
f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
return map("".join, itertools.product(*map(f, S)))