print factors

printFactors(int n)

input:32
  output:
    1 * 32
    2 * 16
    2 * 2 * 8
    2 * 2 * 2 * 4
    2 * 2 * 2 * 2 * 2
    2 * 4 * 4
    4 * 8


Answer:
  vector<vector<int> > printFactors(int n) {
    vector<vector<int> > results;
    vector<int> result;
    recur(n, 2, results, result);
    return results;
}
void recur(int n, int start, vector<vector<int> > &results, vector<int> &result)
{
    if (n == 1) {
        results.push_back(result);
        return;
    }
    for (int i = start; i <= n; ++i) {
        if (n%i == 0) {
            result.push_back(i);
            recur(n/i, i, results, result);
            result.pop_back();
        }
    }
}

Word Break II

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if (!wordBreakPossible(s, dict)) return res;
        wordBreakRe(s, dict, 0, "", res);
        return res;
    }
   
    void wordBreakRe(const string &s, const unordered_set<string> &dict,
                     int start, string sentence, vector<string> &res) {
        if (start == s.size()) {
            res.push_back(sentence);
            return;
        }
        if (start != 0) sentence.push_back(' ');
        for (int i = start; i < s.size(); ++i) {
            string word = s.substr(start, i-start+1);
            if (dict.find(word) == dict.end())
                continue;
            wordBreakRe(s, dict, i+1, sentence + word, res);
        }
    }
   
    bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {
        int N = s.size();
        bool canBreak[N+1];
        memset(canBreak, false, sizeof(canBreak));
        canBreak[0] = true;
        for (int i = 1; i <= N; ++i) {
            for (int j = i-1; j >= 0; --j) {
                if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[N];
    }
};

//another flavor
class Solution {
public:
//From right to left, compute the start index such that the substring[start ,current] is in the dictionary. Then backtrace from the beginning.
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<list<int>> mark(s.length(),list<int>());
        for(int stop=s.length();stop>=0;stop--){
            if(stop<s.length()&&mark[stop].empty()) continue;
            for(int start=stop-1;start>=0;start--){
                if(dict.count(s.substr(start,stop-start)))
                    mark[start].push_back(stop);
            }
           
        }
           
        vector<string> result;
        collect(mark,0,s,"",result);
        return result;
   
    }
    void collect(vector<list<int>>& mark, int ind, const string& s,
                string path, vector<string>& result){
        for(auto& stop:mark[ind]){
            string sub =s.substr(ind,stop-ind);
            string newpath=path+(ind==0?sub:" "+sub);
            if(stop==s.length()) result.push_back(newpath);
            else collect(mark,stop,s,newpath,result);
        }           
   
    }
};

Generate Parentheses

dfs backtracking  经验： 如果dfs函数的参数是pass by reference, 那么在递归调用后，要做恢复现场的工作，如下面函数中对com 和lcnt的操作。 如果dfs函数的参数是pass by value, 那么在递归调用后，就可以不用再作处理了，如flavor 3 中的参数。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        int lcnt=0;
        string com="";
        help(n,ret,com,lcnt);
        return ret;
    }
    void help(int n, vector<string>&ret, string&com, int &lcnt){
        if(lcnt<com.length()-lcnt||lcnt>n){
            return;
        }
        if(com.length()==2*n){
            ret.push_back(com);return;
        }
        com.push_back('(');
        lcnt++;
        help(n,ret,com,lcnt);
        com.pop_back();
        lcnt--;
        com.push_back(')');
        help(n,ret,com,lcnt);
        com.pop_back();//don't forget this!
    }
};

// flavor 2
class Solution {
public:
    vector<string> generateParenthesis(int n) {
       
        vector<string> ret;
        string com="";
        generateParenthesisRe(0,0,n,com,ret);
        return ret;
       
    }
   
    void generateParenthesisRe(int left, int right, int n,string& com,vector<string>&ret){
        if(left==n&&right==n){
            ret.push_back(com);
            return;
        }
        if(left>n||right>n)
            return;
        if(left>right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
            com.push_back(')');
            generateParenthesisRe(left,right+1,n,com,ret);
            com.pop_back();           
        }
        else if(left==right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
        }
           
    }
};

//flavor 3
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        generator(ret,"",0,0,n);
        return ret;
    } 
    void generator(vector<string> & ans, string s, int l, int r, int n){
   
        if(l>n||r>n)
            return;
        if(l==n&&r==n)
            ans.push_back(s);
        generator(ans,s+"(",l+1,r,n);
        if(l>r)
            generator(ans,s+")",l,r+1,n);
    }

};

Combinations

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<int> com;
        vector<vector<int> >res;
       if(n<=0 || n<k)
        return res;
        combineRe(n,1,k,com,res);
        return res;
       
    }
    void combineRe(int n,int start, int k,vector<int>& com,vector<vector<int> >&res){
        if(k==com.size()){
            res.push_back(com);
            return;
        }
        for(int i=start;i<=n;i++){
            com.push_back(i);
            combineRe(n,i+1,k,com,res);
            com.pop_back();
        }
    }
   
};


//second one by anniekim, almost the same as above.
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        vector<int> com;
        combineRe(n, k, 1, com, res);
        return res;
    }
    void combineRe(int n, int k, int start, vector<int> &com, vector<vector<int> > &res){
        int m = com.size();
        if (m == k) {
            res.push_back(com);
            return;
        }
        for (int i = start; i <= n-(k-m)+1; ++i) {
            com.push_back(i);
            combineRe(n, k, i+1, com, res);
            com.pop_back();
        }
    }
};

Combination Sum II

class Solution {

public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        vector<int> com;
        combinationSumRe(candidates, target, 0, com, res);
        return res;
    }

    void combinationSumRe(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res)
    {
        if (target < 0) { return; }

        if (target == 0) {
            res.push_back(com);
            return;
        }
        for (int i = start; i < num.size(); ++i) {
            if(i>start&&num[i]==num[i-1]) continue;//attention, here it is i>start, not i>0
            com.push_back(num[i]);
            combinationSumRe(num, target-num[i], i+1, com, res);
            com.pop_back();
           
        }
    }
};

Combination Sum

class Solution {
public:
     vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> res;
        vector<int> com;
        sort(candidates.begin(),candidates.end());
        combinationSumRe(candidates,0,target,com,res);
        return res;
     }
//注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。
 void combinationSumRe(vector<int> &candidates,int start, int target,vector<int>&com, vector<vector<int>>&res){
         if(target==0){
             res.push_back(com);return;
         }
         for(int i=start;i<candidates.size()&&target>=candidates[i];i++){
             if(i>0&&candidates[i]==candidates[i-1])continue;
             com.push_back(candidates[i]);
             combinationSumRe(candidates,i,target-candidates[i],com,res);
             com.pop_back();
         }
     }

};

N-Queens II

 almost the same as  N-Queens

class Solution {
public:
    int totalNQueens(int n) {
        int ans=0;
        vector<int> C(n,0);
        search(0,n,C,ans);
        return ans;
       
    }
    void search(int row,int n ,vector<int> &C, int& ans){
        if(row==n){
            ans++;
            return;
        }
        for(int i=0;i<n;i++){
            C[row]=i;
            if(check(row,C))
                search(row+1,n,C,ans);
        }
       
    }
    bool check(int row,vector<int> &C){
        for(int i=0;i<row;i++)
            if(C[i]==C[row]||C[i]-C[row]==row-i||C[row]-C[i]==row-i)
                return false;
        return true;       
    }
};

N-Queens

 //dfs

class Solution {

public:
    vector<vector<string> > solveNQueens(int n){
        vector<vector<string> > ans;
        vector<int> C(n,-1);
        search(0, n, C, ans);
        return ans;
    }
    void search(int cur, int n, vector<int>&C, vector<vector<string> > &ans){
        if(cur == n){
            vector<string> vs;
            for(int i=0; i<n; ++i){
                string s(n, '.');
                s[C[i]] = 'Q';
                vs.push_back(s);
            }
            ans.push_back(vs);
            return;
        }
        for(int i=0; i<n; ++i){
            bool ok = true;
            C[cur] = i;
            for(int j=0; j<cur; ++j)
                if(C[cur]==C[j] || cur-j==C[cur]-C[j] || cur-j==C[j]-C[cur]){
                    ok = false;
                    break;
                }
            if(ok) search(cur+1, n, C, ans);
        }
    }
};

// almost the same

class Solution {

public:
    vector<vector<string> > solveNQueens(int n){
        vector<vector<string> > ans;
        vector<int> columnsforrow(n,0);
        search(0,n,columnsforrow,ans);
        return ans;
    }
    void search(int row, int n, vector<int>& columnsforrow,vector<vector<string> >&ans){
        if(row==n){
           
            vector<string> ones;
            for(int i=0;i<n;i++){
                string s(n,'.');
                s[columnsforrow[i]]='Q';
                ones.push_back(s);
            }
            ans.push_back(ones);
            return;
        }
        for(int i=0;i<n;i++){
            columnsforrow[row]=i;
            if(check(row,columnsforrow))
                search(row+1,n,columnsforrow,ans);
        }  
    }
    bool check(int row,vector<int>& columnsforrow){
        for(int i=0;i<row;i++)
            if(columnsforrow[row]==columnsforrow[i]||
            columnsforrow[row]-columnsforrow[i]==row-i||
            columnsforrow[i]-columnsforrow[row]==row-i)
                return false;
        return true;       
    }

};

Palindrome Partitioning

//dfs, backtraking

    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> part;
        partitionRe(s, 0, part,res);
        return res;
    }
    void partitionRe(const string &s, int start, vector<string> &part,vector<vector<string>> &res) {
        if (start == s.size())
        {
            res.push_back(part);
            return;
        }
        string palindrom;
        for (int i = start; i < s.size(); ++i) {
            palindrom.push_back(s[i]);
            if (!isPalindrome(palindrom)) continue;
            part.push_back(palindrom);
            partitionRe(s, i + 1, part,res);
            part.pop_back();
        }
    }
    bool isPalindrome(const string &s) {
        int i = 0, j = s.size()-1;
        while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
        }
        return true;
    }