Bitmask and backtrack

1286. Iterator for Combination

1286. Iterator for Combination

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

Bitmasking solution

// 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();
 */

Recursion method for reference

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();
 */