All k-Element Combinations From 1..n

medium backtracking combinations

Problem

Return every strictly increasing length-k sequence from 1..n. The result is C(n, k) tuples.

Recurse with the next allowed start. At each level, iterate i = start..n, append i, recurse with start i + 1, then pop. Pruning: stop the loop early when the remaining numbers cannot fill the remaining slots, i.e. when i > n - (k - len) + 1.

Inputn = 4, k = 2

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

Six combinations — C(4,2). Order within a tuple is increasing; the recursion guarantees this.

def combine(n, k):
    out, path = [], []
    def back(start):
        if len(path) == k:
            out.append(path.copy()); return
        end = n - (k - len(path)) + 1
        for i in range(start, end + 1):
            path.append(i)
            back(i + 1)
            path.pop()
    back(1)
    return out

function combine(n, k) {
  const out = [], path = [];
  function back(start) {
    if (path.length === k) { out.push(path.slice()); return; }
    const end = n - (k - path.length) + 1;
    for (let i = start; i <= end; i++) {
      path.push(i);
      back(i + 1);
      path.pop();
    }
  }
  back(1);
  return out;
}

List<List<Integer>> out = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
    back(1, n, k);
    return out;
}
void back(int start, int n, int k) {
    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
    int end = n - (k - path.size()) + 1;
    for (int i = start; i <= end; i++) {
        path.add(i);
        back(i + 1, n, k);
        path.remove(path.size() - 1);
    }
}

vector<vector<int>> out;
vector<int> path;
void back(int start, int n, int k) {
    if ((int)path.size() == k) { out.push_back(path); return; }
    int end = n - (k - (int)path.size()) + 1;
    for (int i = start; i <= end; i++) {
        path.push_back(i);
        back(i + 1, n, k);
        path.pop_back();
    }
}
vector<vector<int>> combine(int n, int k) {
    back(1, n, k);
    return out;
}

Time: O(C(n, k) · k) Space: O(k) recursion