Frontend School

Generate Combinations of K Numbers

DSA
easy

Generate Combinations of K Numbers

Easy
Backtracking
Arrays

Overview

In many real-world scenarios, we need to select a specific number of items from a larger pool without regard to their order. For instance, choosing k team members from n candidates, or selecting k ingredients for a recipe from n available options. This problem focuses on generating all such unique selections, known as combinations.

What you need to do / Task

Your task is to implement a function combine that takes two integers, n and k, as input. This function should return all possible unique combinations of k numbers chosen from the range [1, n] (inclusive).

Input & output

  • Input:
    • n: An integer representing the upper limit of the numbers to choose from (i.e., numbers are 1, 2, ..., n).
    • k: An integer representing the size of each combination.
  • Output:
    • A number[][] (or Array<Array<number>>) where each inner array is a unique combination of k numbers. The order of numbers within a combination does not matter, but the order of combinations in the output array does not matter.

Clarifications

  • The numbers to choose from are always 1, 2, ..., n.
  • Each combination must contain k unique numbers.
  • The order of numbers within a combination does not matter (e.g., [1, 2] is the same combination as [2, 1]). Your output should not contain duplicates of the same combination.
  • You can assume 1 <= k <= n.

Examples

1

Example 1

Input:

n = 4, k = 2

Output:

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

Note:

From numbers [1, 2, 3, 4], we need to pick 2. These are all unique pairs.

2

Example 2

Input:

n = 1, k = 1

Output:

[[1]]

Note:

From number [1], we need to pick 1. Only one combination is possible.

3

Example 3

Input:

n = 3, k = 3

Output:

[[1,2,3]]

Note:

From numbers [1, 2, 3], we need to pick 3. Only one combination is possible.

Constraints

Constraints & assumptions

  • 1 <= k <= n <= 9
  • The numbers 1 to n are positive integers.

Out of scope

  • Handling invalid inputs (e.g., k > n, n < 1). Assume valid inputs as per constraints.
  • Optimizations beyond a standard backtracking approach.

What interviewers evaluate

  • Correctness: Does the solution correctly identify all unique combinations of k numbers from n?
  • Algorithm Design: Is a backtracking approach correctly applied to explore the solution space?
  • Edge Cases: Are base cases and termination conditions for the recursion handled appropriately?
  • Code Quality: Is the code clean, readable, and well-structured, demonstrating good software engineering practices?

Loading editor...