Iterator for Combination

medium backtracking design string

Problem

Design a class CombinationIterator built from a string characters of sorted, distinct lowercase letters and an integer combinationLength. It exposes two methods: next() returns the next combination of combinationLength letters in lexicographic order, and hasNext() returns true while combinations remain.

The clean approach is to enumerate every combination up front with backtracking — recurse forward over the characters, keeping picks in increasing index order so the list comes out already sorted — then hand them out one by one with a cursor.

Inputcharacters = "abc", combinationLength = 2

Output"ab", "ac", "bc" (hasNext stays true until all three are returned)

Choosing 2 of {a, b, c} in increasing index order gives exactly ab, ac, bc — already in lexicographic order, so next() simply walks the precomputed list.

characters (sorted distinct letters)

combinationLength

class CombinationIterator:
    def __init__(self, characters, combinationLength):
        self.combos = []
        path = []
        def back(start):
            if len(path) == combinationLength:
                self.combos.append("".join(path)); return
            for i in range(start, len(characters)):
                path.append(characters[i])
                back(i + 1)
                path.pop()
        back(0)
        self.pos = 0

    def next(self):
        c = self.combos[self.pos]
        self.pos += 1
        return c

    def hasNext(self):
        return self.pos < len(self.combos)

class CombinationIterator {
  constructor(characters, combinationLength) {
    this.combos = [];
    const path = [];
    const back = (start) => {
      if (path.length === combinationLength) {
        this.combos.push(path.join("")); return;
      }
      for (let i = start; i < characters.length; i++) {
        path.push(characters[i]);
        back(i + 1);
        path.pop();
      }
    };
    back(0);
    this.pos = 0;
  }
  next() {
    return this.combos[this.pos++];
  }
  hasNext() {
    return this.pos < this.combos.length;
  }
}

class CombinationIterator {
    private List<String> combos = new ArrayList<>();
    private int pos = 0;
    public CombinationIterator(String characters, int combinationLength) {
        back(characters, combinationLength, 0, new StringBuilder());
    }
    private void back(String chars, int len, int start, StringBuilder path) {
        if (path.length() == len) { combos.add(path.toString()); return; }
        for (int i = start; i < chars.length(); i++) {
            path.append(chars.charAt(i));
            back(chars, len, i + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public String next() { return combos.get(pos++); }
    public boolean hasNext() { return pos < combos.size(); }
}

class CombinationIterator {
    vector<string> combos;
    int pos = 0;
    void back(const string& chars, int len, int start, string& path) {
        if ((int)path.size() == len) { combos.push_back(path); return; }
        for (int i = start; i < (int)chars.size(); i++) {
            path.push_back(chars[i]);
            back(chars, len, i + 1, path);
            path.pop_back();
        }
    }
public:
    CombinationIterator(string characters, int combinationLength) {
        string path;
        back(characters, combinationLength, 0, path);
    }
    string next() { return combos[pos++]; }
    bool hasNext() { return pos < (int)combos.size(); }
};

Explanation

The iterator has to hand back combinations in lexicographic order, one per call to next(). The simplest robust design is to generate the whole list in the constructor and then just walk a cursor across it.

Generation is classic backtracking. The helper back(start) tries every character from index start onward. After choosing the character at index i, it recurses with i + 1 so the next pick is always to the right — this guarantees each character is used at most once and that picks stay in increasing index order. When path reaches combinationLength characters, we have a complete combination and append it; then we pop and try the next candidate.

Because the input string is already sorted and we always recurse left-to-right, the combinations come out already sorted — no extra sorting needed. For "abc" with length 2 the recursion visits a→b, a→c, then b→c, producing ["ab", "ac", "bc"].

With the list precomputed, the two methods are trivial. next() returns combos[pos] and advances the cursor. hasNext() simply checks whether pos is still inside the list. Each call is O(L) to copy the string (or O(1) plus the copy), with no recomputation.

If memory is a concern you could instead store only the current index set and advance it like an odometer on each next(), but precomputing keeps the logic clear and the calls fast.

Time: O(C(n, L) · L) build, O(1) per next/hasNext Space: O(C(n, L) · L)