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

Print all combinations | Set-2

Medium ArrayTwo Pointers GeeksforGeeks

Given an array of n elements, generate and print all possible combinations of r elements. The combinations should be printed in sorted order — pick elements left to right without going back.

Example 1:

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

Example 2:

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

Example 3:

Input: arr = [1, 2, 3, 4, 5], r = 1
Output: [1], [2], [3], [4], [5]

Edge cases: r = 0 returns one empty combination. r > n returns no combinations. r = n returns the full array as the only combination.

Sample Input
arr = [1, 2, 3, 4], r = 2
Sample Output
[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
Constraints
  • 1 <= N <= 20
  • 1 <= k <= N
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.

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(r) for the recursion depth (excluding output storage)

Saved in this browser only. Private to you.

JavaScript