LIKE CODING: MJ [48] Compute combinations

LIKE CODING: MJ [48] Compute combinations
Given a 2-D vector of strings [[Hello, Hi], [world, girl, boy]]
print:
Hello world
Hello girl
Hello boy
Hi world
Hi girl
Hi boy

    vector<vector<string>> getCombinations_rec(vector<vector<string>> strs){

        vector<vector<string>> ret;

        dfs(ret, vector<string>(), 0, strs.size(), strs);

        return ret;

    }

    void dfs(vector<vector<string>> &ret, vector<string> cur, int pos, int n, vector<vector<string>> &strs){

        if(pos==n){

            ret.push_back(cur);

        }else{

            for(int i=0; i<strs[pos].size(); ++i){

                cur.push_back(strs[pos][i]);

                dfs(ret, cur, pos+1, n, strs);

                cur.pop_back();

            }

        }

    }

 

    bool increase1(vector<int> &index, vector<vector<string>> &strs, int n){

        for(int i=0; i<n; ++i){

            if(index[i]<(int)strs[i].size()-1){

                index[i] += 1;

                return true;

            }else{

                index[i] = 0;

            }

        }

        return false;

    }

    vector<vector<string>> getCombinations_ite(vector<vector<string>> strs){

        int n = strs.size();

        vector<int> index(n, 0);

 

        vector<vector<string>> ret;

        while(true){

            PrintVector(index, "index");

            vector<string> cur(n);

            for(int i=0; i<n; ++i){

                cur[i] = strs[i][index[i]];

            }

            ret.push_back(cur);

            if(!increase1(index, strs, n)) break;

        }

 

        return ret;

    }

};

 

int main(){

    vector<vector<string>> strs = {{"a","b","c","d"},{"1","2"},{"x", "y", "z"}};

    Solution sol;

    vector<vector<string>> ret;

    ret = sol.getCombinations_rec(strs);

    PrintVV(ret, "ret");

    ret = sol.getCombinations_ite(strs);

    PrintVV(ret, "ret");

    return 0;

}

http://www.mitbbs.com/article_t/JobHunting/32972467.html
给出了recursive解法，有个地方忘写return了被指出，改正
followup： how to do it iteratively？
1.add one to integer list
例如 [2， 0， 1， 5] -> [2, 0 , 1, 6]
[2， 0， 1， 9] -> [2, 0 , 2, 0]

记得处理corner case [9， 9， 9]
Read full article from LIKE CODING: MJ [48] Compute combinations