Medium

Combinations

LAB

Return all k-number combinations chosen from 1 through n, sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "n": 4,
  "k": 2
}

Output
[
  [
    1,
    2
  ],
  [
    1,
    3
  ],
  [
    1,
    4
  ],
  [
    2,
    3
  ],
  [
    2,
    4
  ],
  [
    3,
    4
  ]
]

FUNCTION SHAPE

n: intk: int→intMatrix

Reveal reference solution +

pythonREFERENCE

def combine(self, n: int, k: int) -> List[List[int]]:
    res = []
    curr = []

    def backtrack(i):
        if len(curr) == k:
            res.append(curr.copy())
        else:
            for j in range(i, n+1):
                curr.append(j)
                backtrack(j+1)
                curr.pop()

    backtrack(1)
    return res

TimeO(n * C(n,k))

SpaceO(n * C(n,k))

Open on LeetCode ↗