1286. Iterator for Combination

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

Iterator for Combination - LeetCode

 

class CombinationIterator {
public:
    int n;
    int k;
    
    vector<string> combinations;
    
    void backtrack(string& characters, int pos, string s, int k){
        int n = characters.size();
        
        if(k == s.size()){
            combinations.push_back(s);
            return;
        }
        
        if(n == pos){
            return;
        }
        
        backtrack(characters, pos + 1, s, k);
        backtrack(characters, pos + 1, s + characters[pos], k);
        return;
    }
    
    CombinationIterator(string characters, int combinationLength) {
        this->n = characters.size();
        this->k = combinationLength;
        
        backtrack(characters, 0, "", this->k);
        int v = 1;
    }
    
    string next() {
        string 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 {
public:
    int n;
    int k;
    
    vector<string> combinations;
    
    CombinationIterator(string characters, int combinationLength) {
        this->n = characters.size();
        this->k = combinationLength;
        
        for(int bitmask = 0; bitmask < 1 << n; bitmask++){
            int cnt = bitCount(bitmask);
            if(cnt == k){
                string curr = "";
                
                for(int j = 0; j < n; j++){
                    if((bitmask & (1 << n - j - 1)) != 0){
                        curr += characters[j];
                    }
                }
                combinations.push_back(curr);
            }
        }
    }
    
    int bitCount(int bitmask){
        int ret = 0;
        
        for(int i = 0; i < 15; i++){
            ret += bitmask & 1;
            bitmask = bitmask >> 1;
        }
        return ret;
    }
    
    string next() {
        string 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();
 */