#1286

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Iterator for Combination

Implement an iterator that generates all combinations of a given length using efficient backtracking with pruning.

Problem Statement

Design a CombinationIterator class for a string of unique characters and a fixed combination length. The iterator should return combinations in lexicographical order and support next() and hasNext() operations efficiently.

Implement the class with the following behavior: next() returns the next combination string, hasNext() checks if more combinations are available, and all operations must be optimized for multiple calls while adhering to the constraints on input size and uniqueness.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [["abc", 2], [], [], [], [], [], []] Output [null, "ab", true, "ac", true, "bc", false]

Explanation CombinationIterator itr = new CombinationIterator("abc", 2); itr.next(); // return "ab" itr.hasNext(); // return True itr.next(); // return "ac" itr.hasNext(); // return True itr.next(); // return "bc" itr.hasNext(); // return False

Constraints

1 <= combinationLength <= characters.length <= 15
All the characters of characters are unique.
At most 104 calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Solution Approach

Precompute all combinations with backtracking

Use backtracking to generate all valid combinations of the given length. Apply pruning by skipping branches once the remaining characters cannot fulfill the required combination length. Store results in a queue or list to support fast iteration through next().

Use an index pointer for iteration

Maintain an internal pointer to track the current combination in the precomputed list. next() increments the pointer and returns the combination, while hasNext() checks if the pointer is still within bounds. This avoids recomputation and guarantees O(1) per call.

Optimize memory and call limits

Given the constraints on string length and number of calls, ensure that precomputing all combinations is feasible. Avoid storing redundant data and leverage lazy evaluation only if needed to reduce space usage while maintaining constant-time next() access.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(C(n, k)) to precompute all combinations, where n is characters.length and k is combinationLength. Each next() and hasNext() call is O(1). Space complexity is also O(C(n, k)) to store all combinations for efficient iteration.

What Interviewers Usually Probe

They may ask about handling large input strings and optimizing precomputation.
Expect clarification questions on lexicographical ordering and index management.
They may probe memory trade-offs between storing all combinations versus generating on the fly.

Common Pitfalls or Variants

Common pitfalls

Failing to prune branches during backtracking, leading to unnecessary computation.
Incorrect pointer management causing next() to skip or repeat combinations.
Ignoring lexicographical order in the combination generation.

Follow-up variants

Generate combinations lazily without precomputing to reduce memory usage.
Allow duplicate characters in the input string, requiring additional checks.
Support variable-length combinations instead of a fixed length.

FAQ

What is the main pattern in Iterator for Combination?

The key pattern is backtracking search with pruning to generate all combinations efficiently and in lexicographical order.

How do I ensure next() and hasNext() are fast?

Precompute all combinations using backtracking and store them in a list or queue, allowing O(1) next() and hasNext() operations.

What should I watch out for with lexicographical order?

Maintain the order during backtracking by always choosing characters in increasing index order to ensure correct sequence generation.

Can this approach handle maximum input constraints?

Yes, with n <= 15, precomputing all C(n, k) combinations is feasible and fits within memory limits.

Is lazy combination generation better than precomputing?

Lazy generation saves space but adds complexity; for this problem, precomputing is preferred to achieve constant-time iteration.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        def dfs(i):
            if len(t) == combinationLength:
                cs.append(''.join(t))
                return
            if i == n:
                return
            t.append(characters[i])
            dfs(i + 1)
            t.pop()
            dfs(i + 1)

        cs = []
        n = len(characters)
        t = []
        dfs(0)
        self.cs = cs
        self.idx = 0

    def next(self) -> str:
        ans = self.cs[self.idx]
        self.idx += 1
        return ans

    def hasNext(self) -> bool:
        return self.idx < len(self.cs)


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        def dfs(i):
            if len(t) == combinationLength:
                cs.append(''.join(t))
                return
            if i == n:
                return
            t.append(characters[i])
            dfs(i + 1)
            t.pop()
            dfs(i + 1)

        cs = []
        n = len(characters)
        t = []
        dfs(0)
        self.cs = cs
        self.idx = 0

    def next(self) -> str:
        ans = self.cs[self.idx]
        self.idx += 1
        return ans

    def hasNext(self) -> bool:
        return self.idx < len(self.cs)


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Continue Practicing

#1307 verbal arithmetic puzzle #1255 maximum score words formed by letters #1239 maximum length of a concatenated string with unique characters