Combinations Medium 0 attempts
LeetCode ↗

Combinations

Medium BacktrackingRecursion LeetCode

Given integers n and k, generate every possible way to pick k numbers out of the range [1, n], returning them as a list of combinations in any order.

Order within a combination doesn't matter — picking 1 then 2 is the same selection as picking 2 then 1, so each such group should appear only once.

Input Format
Implement combine(n, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Result ordering is ignored, including element order within each combination or subset.

Sample Input and Output

Example 1 · Run Sample

Input
n = 4
k = 2
Output
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2

Input
n = 1
k = 1
Output
[[1]]
Constraints
  • 1 <= n <= 20
  • 1 <= k <= n
Test Cases (2)
Case 1
Args: [4,2] Expected: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Case 2
Args: [1,1] Expected: [[1]]
Topics
BacktrackingRecursion

Backtrack through choices starting from 1. At each step, pick a number greater than the last chosen one and recurse with k - 1. When k reaches 0, save the current combination. An optimization: stop early if there aren't enough numbers left to fill the remaining slots.

javascript
function combine(n, k) {
  const result = [];

  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    const remaining = k - current.length;
    for (let i = start; i <= n - remaining + 1; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(1, []);
  return result;
}

Time: O(C(n, k) * k) — there are C(n, k) combinations, each taking O(k) to copy. Space: O(k) for the recursion stack.

Saved in this browser only. Private to you.

JavaScript