Combination Generator

Generate all k-length combinations from a list of distinct integers using recursion.

recursion backtracking combinations lists

Write a function `combinations(nums, k)` that takes a list of distinct integers `nums` and an integer `k` (0 <= k <= len(nums)). The function should return a list of all possible combinations of length `k` from `nums`. Each combination should be a list of integers in the same relative order as they appear in `nums`. The list of combinations should be in lexicographic (dictionary) order based on the original order of `nums`. Use recursion (backtracking) to solve the problem.

Define the function signature exactly as:
```
def combinations(nums, k):
    pass
```

For example, if `nums = [1, 2, 3]` and `k = 2`, the output should be `[[1, 2], [1, 3], [2, 3]]`.

You may assume all integers in `nums` are unique. The order matters only as described above.

Constraints

- `0 <= k <= len(nums) <= 15` (small sizes, recursion is fine)
- `nums` contains distinct integers.
- Output size is C(n, k) which may be large but within reasonable limits for small n.
- Your solution must use recursion (backtracking) – no itertools.combinations.

Example

>>> combinations([1, 2, 3], 2)
[[1, 2], [1, 3], [2, 3]]
>>> combinations([1, 2, 3], 3)
[[1, 2, 3]]
>>> combinations([1, 2, 3], 0)
[[]]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a recursive helper that builds a combination step by step. The base case is when k == 0: return a list containing an empty list.

For each index i, include nums[i] and then recursively choose k-1 elements from the remaining elements that come after i.

To maintain order, only recurse on the sublist nums[i+1:]. Concatenate results from all starting positions.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.