Leetcode: Combinations
Given two integers n and k, create all possible solutions with all numbers from [1,n] of k length.
This can be solved via recursion. An added complication is to remove duplicate paths ([1,2] == [2,1]). To avoid this, we can start the next number always from the number higher than the last highest number.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
paths = []
self.inner(n, k, [], paths)
return paths
def inner(self, n: int, k: int, path: List[int], paths: List[List[int]]):
if k == 0:
paths.append(path)
return
if len(path) > 0:
lower = path[-1] + 1
else:
lower = 1
for i in range(lower, n + 1):
self.inner(n, k - 1, path + [i], paths)