TNotes.leetcode

Appearance

0077. 组合【中等】

0077. 组合【中等】 ​

1. 📝 题目描述 ​

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

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

示例 1：

输入：n = 4, k = 2
输出：
[
  [2, 4], [3, 4], [2, 3],
  [1, 2], [1, 3], [1, 4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

2. 🎯 s.1 - 回溯 + 剪枝 ​

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** answers;
int answerSize;
int limitN;
int targetK;
int path[20];
int pathSize;

int getCombinationCount(int n, int k) {
	if (k > n - k) k = n - k;
	long long count = 1;
	for (int i = 1; i <= k; i++) {
		count = count * (n - k + i) / i;
	}
	return (int)count;
}

void backtrack(int start, int* returnColumnSizes) {
	if (pathSize == targetK) {
		int* combination = (int*)malloc(targetK * sizeof(int));
		for (int i = 0; i < targetK; i++) combination[i] = path[i];
		answers[answerSize] = combination;
		returnColumnSizes[answerSize] = targetK;
		answerSize++;
		return;
	}

	for (int num = start; num <= limitN - (targetK - pathSize) + 1; num++) {
		path[pathSize++] = num;
		backtrack(num + 1, returnColumnSizes);
		pathSize--;
	}
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
	int total = getCombinationCount(n, k);
	answers = (int**)malloc(total * sizeof(int*));
	*returnColumnSizes = (int*)malloc(total * sizeof(int));
	answerSize = 0;
	limitN = n;
	targetK = k;
	pathSize = 0;

	backtrack(1, *returnColumnSizes);

	*returnSize = answerSize;
	return answers;
}
js
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const ans = []
  const path = []

  const backtrack = (start) => {
    if (path.length === k) {
      ans.push([...path])
      return
    }

    for (let num = start; num <= n - (k - path.length) + 1; num++) {
      path.push(num)
      backtrack(num + 1)
      path.pop()
    }
  }

  backtrack(1)
  return ans
}
py
class Solution:
	def combine(self, n: int, k: int) -> List[List[int]]:
		ans: List[List[int]] = []
		path: List[int] = []

		def backtrack(start: int) -> None:
			if len(path) == k:
				ans.append(path[:])
				return

			for num in range(start, n - (k - len(path)) + 2):
				path.append(num)
				backtrack(num + 1)
				path.pop()

		backtrack(1)
		return ans
  • 时间复杂度：O(k×C(n,k))，一共需要生成 C(n,k) 个长度为 k 的组合，每次加入答案都要复制当前路径
  • 空间复杂度：O(k)，递归栈深度和当前路径长度都不会超过 k；若计入返回结果，总空间为 O(k×C(n,k))

算法思路：

  • 用 path 记录当前已经选出的组合，用 start 表示下一次只能从哪个数字开始选，保证组合中的元素严格递增，从而避免重复
  • 每次从区间 [start, n] 中挑一个数字加入 path，然后递归去选择下一个数字
  • 当 path 的长度等于 k 时，说明已经构造出一个合法组合，将其拷贝加入答案

2.1. 剪枝策略 ​

path.length 表示当前已经固定的数字的数量，还差 x 个数字凑满 k 个数，x = k - path.length。

如果当前枚举的起点太靠后，后面剩余数字数量（小于 x）不足以凑满长度为 k 的组合，就没有继续搜索的必要。

边界区间：

  • [n - x + 1, n] => 这段区间的数字全算上，一共 x 个数字，正好可以让 path.length 凑满 k 个数
  • [n - x + 2, n] => 这段区间的数字全算上，一共 x - 1 个数字

综上：循环上界可以写成 n - (k - path.length) + 1（可以取到）。

这种剪枝不会改变结果，只是提前跳过不可能得到合法组合的分支，提高搜索效率。

Discussions