如何将LeetCode77的回溯组合生成代码转换为迭代器？

原回溯代码（LeetCode 77 参考） #

先回顾你原本实现的LeetCode 77回溯解法，通常是这样的：

def combine(n: int, k: int) -> list[list[int]]:
    res = []
    def backtrack(start, path):
        if len(path) == k:
            res.append(path.copy())
            return
        for i in range(start, n+1):
            path.append(i)
            backtrack(i+1, path)
            path.pop()
    backtrack(1, [])
    return res

转换为Generator版本 #

要改成逐个生成组合的生成器，只需要修改结果收集逻辑，把res.append替换为yield，同时用yield from传递递归生成的结果，核心回溯逻辑完全保留：

from typing import Generator, List

def combination_generator(n: int, k: int) -> Generator[List[int], None, None]:
    def backtrack(start, path):
        if len(path) == k:
            yield path.copy()  # 找到有效组合时直接返回，而非存入列表
            return
        for i in range(start, n+1):
            path.append(i)
            yield from backtrack(i+1, path)  # 迭代递归生成的所有子结果
            path.pop()  # 回溯，移除当前元素
    yield from backtrack(1, [])

适配LeetCode 1286的Iterator类 #

如果需要严格符合LeetCode 1286的迭代器接口（支持next()和hasNext()方法），可以把生成器包装成类，通过预取下一个值实现接口：

from typing import Generator, List

class CombinationIterator:
    def __init__(self, n: int, k: int):
        self.generator = self._combination_generator(n, k)
        self._next_val = None
        self._prefetch()  # 预取第一个组合，用于hasNext判断

    def _combination_generator(self, n: int, k: int) -> Generator[List[int], None, None]:
        def backtrack(start, path):
            if len(path) == k:
                yield path.copy()
                return
            for i in range(start, n+1):
                path.append(i)
                yield from backtrack(i+1, path)
                path.pop()
        yield from backtrack(1, [])

    def _prefetch(self):
        try:
            self._next_val = next(self.generator)
        except StopIteration:
            self._next_val = None

    def next(self) -> List[int]:
        current_val = self._next_val
        self._prefetch()  # 预取下一个组合
        return current_val

    def hasNext(self) -> bool:
        return self._next_val is not None

关键修改说明 #

1. 替换结果收集方式：原代码用列表存储所有组合，现在用yield逐个返回，避免一次性占用大量内存。
2. 递归传递生成器：递归调用回溯函数时，必须用yield from来迭代子递归生成的所有结果，确保每个子组合都能传递到顶层。
3. 保留原回溯逻辑：核心的遍历、选择、递归、回溯流程完全不变，只是调整了结果输出方式，保持了原代码的简洁性。

内容的提问来源于stack exchange，提问作者Abhijit Sarkar