# 1286. Iterator for Combination

Design the `CombinationIterator` class:

• `CombinationIterator(string characters, int combinationLength)` Initializes the object with a string `characters` of sorted distinct lowercase English letters and a number `combinationLength` as arguments.
• `next()` Returns the next combination of length `combinationLength` in lexicographical order.
• `hasNext()` Returns `true` if and only if there exists a next combination.

Example 1:

``````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.

a b c
0 0 0 -> “”
0 0 1 -> c
0 1 0 -> b
0 1 1 -> bc
1 0 0 -> a
1 0 1 -> ac
1 1 0 -> ab
1 1 1 -> abc

``````class CombinationIterator {
public:
CombinationIterator(string characters, int combinationLength) {
st = generateAll(characters, combinationLength);
cur = begin(st);
}
string next() {
return cur == end(st) ? "" : *cur++;
}
bool hasNext() {
return cur != end(st);
}

private:
set<string> st;
set<string>::iterator cur;

set<string> generateAll(string str, int len) {
set<string> res;
int n = 1 << str.size();
string t = "";
for (int i = 0; i < str.size(); ++i) {
if (mask & (1 << i)) t += str[i];
}
if (t.size() == len) res.insert(t);
}
return res;
}
};
``````

``````class CombinationIterator {
public:
CombinationIterator(string characters, int combinationLength) {
generateAll(characters, combinationLength, 0, "");
cur = begin(st);
}
string next() {
return cur == end(st) ? "" : *cur++;
}
bool hasNext() {
return cur != end(st);
}

private:
set<string> st;
set<string>::iterator cur;

void generateAll(string str, int len, int start, string res) {
if (len == 0) {
st.insert(res);
return;
}
for (int i = start; i <= (int)str.size() - len; ++i) {
generateAll(str, len - 1, i + 1, res + str[i]);
}
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1286

https://leetcode.com/problems/iterator-for-combination/

https://leetcode.com/problems/iterator-for-combination/discuss/451322/(JAVA)-Generate-Combinations

https://leetcode.com/problems/iterator-for-combination/discuss/451368/C%2B%2B-solution-with-multiple-pointers

https://leetcode.com/problems/iterator-for-combination/discuss/789164/C%2B%2B-Using-Bit-manipulation-or-Detail-Explain

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation