Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 77 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 77 # by problem number
lcpy gen -s combinations # by problem name
n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
[1,2] and [2,1] are considered to be the same combination.
Input: n = 1, k = 1
Output: [[1]]
class Solution:
# Time: O(C(n,k) * k)
# Space: O(C(n,k) * k)
def combine(self, n: int, k: int) -> list[list[int]]:
result: list[list[int]] = []
current: list[int] = []
def backtrack(start: int) -> None:
if len(current) == k:
result.append(current[:])
return
# Prune: stop early if not enough remaining numbers to reach k
for num in range(start, n - (k - len(current)) + 2):
current.append(num)
backtrack(num + 1)
current.pop()
backtrack(1)
return result
| Time | Space |
|---|---|
| O(C(n,k) * k) | O(C(n,k) * k) |