1286. 字母组合迭代器

还是套回溯模板，模板可参考：https://www.cnblogs.com/panweiwei/p/14025143.html

class CombinationIterator(object):
    def __init__(self, characters, combinationLength):
        """
        :type characters: str
        :type combinationLength: int
        """
        # 按字典序存放长为combinationLength的所有所有字符串
        self.res = []
        string = list(characters)
        string.sort()
        n = len(string)
        visit = [0 for _ in range(n)]
        self.dfs(string, visit, n, combinationLength, 0, [])

    def dfs(self, string, visit, n, k, cur, temp):
        if len(temp) == k:
            self.res.append("".join(temp))
            return
        for i in range(cur, n):
            if not visit[i]:
                # 长度超范围，结束递归
                if len(temp) > n:
                    break
                visit[i] = 1
                self.dfs(string, visit, n, k, i + 1, temp+[string[i]])
                visit[i] = 0

    def next(self):
        """
        :rtype: str
        """
        return self.res.pop(0)

    def hasNext(self):
        """
        :rtype: bool
        """
        return True if self.res else False