Combinations

Medium

backtracking

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

A combination is a selection of k elements where order does NOT matter. Unlike permutations, [1,2] and [2,1] are the same combination.

The number of ways to choose k items from n items is "n choose k" = n! / (k! * (n-k)!).

To avoid duplicates, we only consider elements in increasing order. When we choose element i, we only look at elements > i for subsequent positions.

Example 1

Input: n = 4, k = 2

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

Explanation: There are 6 ways to choose 2 numbers from [1,2,3,4]. Notice we list in increasing order to avoid duplicates.

Example 2

Input: n = 1, k = 1

Output: [[1]]

Explanation: Only one way to choose 1 number from [1].

Constraints

•1 <= n <= 20
•1 <= k <= n

Show Hints (4)

Hint 1: This is similar to subsets, but we only want subsets of exactly size k.

Hint 2: To avoid duplicates like [1,2] and [2,1], always pick numbers in increasing order.

Hint 3: When you pick number i, the next number must be > i.

Hint 4: You can prune: if you need k more numbers but only have fewer remaining, backtrack early.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?