1286. Iterator for Combination

This is a problem which we can use either backtracking or bit masking method.

// time complexity: 2^n*n^2
class CombinationIterator {
vector<string> combinations;
public:
CombinationIterator(string characters, int combinationLength) {
string this_ret = "";
const int n = characters.length();
for (int i = 0; i < (1<<n); ++i)
{
if (__builtin_popcount(i) == combinationLength)
{
for (int j = n - 1 ; j >=0; --j)
{
if (i&(1<<j)) this_ret.push_back(characters[n-j-1]);
}
combinations.push_back(this_ret);
this_ret.clear();
}
}

}

string next() {
auto ret = combinations.back();combinations.pop_back();
return ret;
}

bool hasNext() {
return !combinations.empty();

}
};
/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
* string param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/
class CombinationIterator {
int i = 0;
vector<string> combinations;
// abc. --> ab
vector<string> get_combinations(string characters, int len)
{
vector<string> ret;
if (characters.length() < len || len == 0) return ret;
if (characters.length() == len) return {characters};
if (len == 1)
{
for (auto c : characters)
{
string s(1, c);
ret.push_back(s);
}

}
else
{
string new_characters = characters.substr(1);
auto this_ret = get_combinations(new_characters, len - 1);
auto this_ret1 = get_combinations(new_characters, len);
for (auto x: this_ret) ret.push_back(characters[0] + x);
for (auto x : this_ret1) ret.push_back(x);

}
return ret;
}
public:
CombinationIterator(string characters, int combinationLength) {

i = 0;
combinations = get_combinations(characters, combinationLength);

}

string next() {
return (combinations[i++]);
}

bool hasNext() {
return i < combinations.size();

}
};
/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
* string param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/

Data Scientist/MLE/SWE @takemobi