77. Combinations
給定兩個整數 n 和 k，返回從範圍 [1, n] 中選擇 k 個數字的所有可能組合。
你可以以任何順序返回答案。
範例 1：
輸入：n = 4, k = 2 輸出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] 解釋：共有 4 選 2 = 6 種組合。 注意組合是無序的，即 [1,2] 和 [2,1] 被視為相同的組合。
Python
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start: int, combination: List[int]):
# If the combination is complete
if len(combination) == k:
result.append(combination[:])
return
for i in range(start, n + 1):
# Add i into the current combination
combination.append(i)
# Use next integers to complete the combination
backtrack(i + 1, combination)
# Backtrack, remove the last element
combination.pop()
result = []
backtrack(1, [])
return result
64.98MB, 714ms
C++
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> combine(int n, int k) {
std::vector<std::vector<int>> result;
std::vector<int> combination;
backtrack(1, n, k, combination, result);
return result;
}
private:
void backtrack(int start, int n, int k, std::vector<int>& combination,
std::vector<std::vector<int>>& result) {
// If the combination is complete
if (combination.size() == k) {
result.push_back(combination);
return;
}
for (int i = start; i <= n; ++i) {
// Add i into the current combination
combination.push_back(i);
// Use next integers to complete the combination
backtrack(i + 1, n, k, combination, result);
// Backtrack, remove the last element
combination.pop_back();
}
}
};
61.81MB, 71ms
Javascript
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const result = [];
const backtrack = (start, combination) => {
// If the combination is complete
if (combination.length === k) {
result.push([...combination]);
return;
}
for (let i = start; i <= n; i++) {
// Add i into the current combination
combination.push(i);
// Use next integers to complete the combination
backtrack(i + 1, combination);
// Backtrack, remove the last element
combination.pop();
}
};
backtrack(1, []);
return result;
};
120.98MB, 431ms
