Print all combinations | Set-2 Medium 0 attempts
GeeksforGeeks ↗

Print all combinations | Set-2

Medium ArrayTwo Pointers GeeksforGeeks

You're given an array of n elements and a target size r. List every combination of r elements drawn from the array, always moving forward through the array (no revisiting earlier positions) preserving the original index order inside each combination. The input need not be sorted; equal values at different indices are separate choices.

Edge cases: With r = 0, the only valid combination is the empty one. If r > n, no combination is possible. If r = n, the entire array is the sole combination.

Input Format
Implement combinations(arr, r). 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.

Sample Input and Output

Example 1 · Run Sample

Input
arr = [1,2,3]
r = 2
Output
[[1,2],[1,3],[2,3]]

Example 2

Input
arr = [1,2]
r = 0
Output
[[]]

Example 3

Input
arr = [1]
r = 2
Output
[]
Constraints
  • 1 <= arr.length <= 20
  • 0 <= r <= 20
Test Cases (3)
Case 1
Args: [[1,2,3],2] Expected: [[1,2],[1,3],[2,3]]
Case 2
Args: [[1,2],0] Expected: [[]]
Case 3
Args: [[1],2] Expected: []
Topics
ArrayTwo Pointers

Approach: Recursive Pick / Skip

At each index, decide: include this element in the current combination or skip it. Move forward either way. When you've picked r elements, record the combination. Stop early if there aren't enough elements left to fill the remaining slots.

javascript
function combinations(arr, r) {
  const results = [];

  function combine(start, current) {
    if (current.length === r) {
      results.push([...current]);
      return;
    }
    if (start >= arr.length) return;
    if (arr.length - start < r - current.length) return;

    current.push(arr[start]);
    combine(start + 1, current);
    current.pop();
    combine(start + 1, current);
  }

  combine(0, []);
  return results;
}

Time Complexity: O(C(n, r) × r) — generating all C(n, r) combinations, each of size r

Space Complexity: O(n) for the pick/skip recursion depth (excluding output storage)

Saved in this browser only. Private to you.

JavaScript