1286. Iterator for Combination

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

`// time complexity: 2^n*n^2class 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

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi