# Backtrack and bit manipulation

• backtrack
• bit manipulation

# Backtrack

`class Solution {    public:    void backtrack(string& s,int i, vector<string>& current,vector<vector<string>>& ret){        const int n = s.size();        // touch the bottom of the backtracking        if (i == n){            if (is_palindrome(current.back())){                ret.push_back(current);            }            return;        }        // put a separate at position i        if (is_palindrome(current.back())){            current.push_back(s.substr(i, 1));            backtrack(s, i + 1, current, ret);            if (current.back().size() > 1){                current.back().pop_back();            } else {                current.pop_back();            }        }        // do not put a separate at position i        current.back().push_back(s[i]);        backtrack(s, i + 1, current, ret);        if (current.back().size() > 1){            current.back().pop_back();        } else {            current.pop_back();        }}    vector<vector<string>> partition(string s) {        vector<vector<string>> ret;        vector<string> current;        current.push_back(s.substr(0, 1));        if (s.size() == 0) return ret;        if (s.size() == 1) {            ret.push_back({s});            return ret;        }        int i = 1;        backtrack(s, i, current, ret);        return ret;}    private:    bool is_palindrome(string& c){        const int n = c.size();        if (n <= 1)return true;        int i = 0, j = n - 1;        while (i < j){            if (c[i++] != c[j--])return false;        }        return true;    }};`

# Bit Manipulation

`class Solution {public:      vector<vector<string>> partition(string s) {        vector<vector<string>> ret;        const int n = s.size() - 1;        for (int i = 0; i < (1 << n); ++i){            vector<string> candidate = _partition(s, i);            if(are_palindromes(candidate)){                ret.push_back(candidate);            }        }        return ret;            }    private:    bool is_palindrome(string& c){        const int n = c.size();        if (n <= 1)return true;        int i = 0, j = n - 1;        while (i < j){            if (c[i++] != c[j--])return false;        }        return true;    }    bool are_palindromes(vector<string>&candidate){        if (candidate.empty())return true;        for (auto & c: candidate){            if (!is_palindrome(c))return false;        }        return true;    }      vector<string> _partition(string s,int mask){          const int n = s.size();          vector<string> ret;          string curr = "";          for (int i = 0; i < n; ++i){              curr += s[i];              if ((1 << i) & mask){                  ret.push_back(curr);                  curr = "";              }          }          ret.push_back(curr);          return ret;      }};`

--

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi