Algorithms & Data Structures : Backtracking Problems

Problem

LeetCode 78. Subsets
[backtracking]

LeetCode 489. Robot Room Cleaner
[backtracking]

LeetCode 1240. Tiling a Rectangle with the Fewest Squares
[backtracking][dynamic programming]

LeetCode 473. Matchsticks to Square
[back tracking][sorting]

LeetCode 90. Subsets II
[back tracking]

LeetCode : 491. Increasing Subsequences
[back tracking]

LeetCode : 2305. Fair Distribution of Cookies
[back tracking][dynamic programming][bit manipulation]

LeetCode : 2375. Construct Smallest Number From DI String
[backtracking][string][greedy]

LeetCode : 1774. Closest Dessert Cost
[backtracking][dynamic programming]

LeetCode : 320. Generalized Abbreviation
[back-tracking]

LeetCode : 1258. Synonymous Sentences
[back-tracking][union-find][hash table][string]

LeetCode : 1255. Maximum Score Words Formed by Letters
[back-tracking][Dynamic Programming][String][Bit Manipulation][Bitmask][Hard]

LeetCode : 1088. Confusing Number II
[back-tracking][hard]

—

LeetCode 79. Word Search

LeetCode 51. N-Queens

LeetCode 78. Subsets

class Solution {
public: 
    void backTrack(int nowLevel, int targetLevel, int lastI, vector<int> &nums, vector<bool> &visited, vector<vector<int>> &res, vector<int> &nowv) {
        if(nowLevel == targetLevel) {
            res.push_back(nowv);
            return;
        }
        
        for(int i = lastI + 1;i < nums.size();i++) {
            if(!visited[i]) {
                visited[i] = true;
                nowv.push_back(nums[i]);
                backTrack(nowLevel + 1, targetLevel, i, nums, visited, res, nowv);
                nowv.pop_back();
                visited[i] = false;
            }
        }
        
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> nowv;
        vector<bool> visited = vector<bool>(nums.size(), false);
        for(int i = 0;i <= nums.size();i++) {
            backTrack(0, i, -1, nums, visited, res, nowv);
        }
        
        return res;
    }
};

LeetCode 489. Robot Room Cleaner

利用 back tracking 去遍尋沒有到過的點。
假如遇到牆壁，就回到原點，面向原來的方向，繼續朝下個方位進行遍尋。

typedef enum {
    UP, 
    RIGHT,
    DOWN,
    LEFT
} DIRECTION;
class Solution {
private:
    unordered_map<int, unordered_map<int, bool>> visited;
    int X[4] = {-1, 0, 1, 0};
    int Y[4] = {0, 1, 0, -1};
    void dfs(int x, int y, int direct, Robot &robot) {
        bool res = false;
        for(int i = 0;i < 4;i++) {
            int newx = x + X[i];
            int newy = y + Y[i];
            
            if(visited[newx][newy]) {
                continue;
            }
            
            visited[newx][newy] = true;
            
            
            int turn = i - direct;
            if(turn == 0) {
                res = robot.move();
                if(res) {
                    robot.clean();
                    dfs(newx, newy, i, robot);
                    robot.turnLeft();
                    robot.turnLeft();
                    robot.move();
                    robot.turnLeft();
                    robot.turnLeft();
                }
            } else if(turn < 0) {
                for(int j = turn;j < 0;j++) {
                    robot.turnLeft();
                }     
                res = robot.move();
                if(res) {
                    robot.clean();
                    dfs(newx, newy, i, robot);
                    robot.turnLeft();
                    robot.turnLeft();
                    robot.move();
                    robot.turnLeft();
                    robot.turnLeft();
                }
                for(int j = turn;j < 0;j++) {
                    robot.turnRight();
                }
            } else if(turn > 0) {
                for(int j = turn;j > 0;j--) {
                    robot.turnRight();
                }
                res = robot.move();
                if(res) {
                    robot.clean();
                    dfs(newx, newy, i, robot);
                    robot.turnLeft();
                    robot.turnLeft();
                    robot.move();
                    robot.turnLeft();
                    robot.turnLeft();
                }
                for(int j = turn;j > 0;j--) {
                    robot.turnLeft();
                }
            }
        }
    }
public:    
    void cleanRoom(Robot& robot) {
        visited[0][0] = true;
        robot.clean();
        dfs(0, 0, UP, robot);
    }
};

LeetCode 1240. Tiling a Rectangle with the Fewest Squares

TODO : 寫的很差，需要想辦法改進，想不出來需要看一下其他人怎麼想的

class Solution {
private:
    bitset<169> panel;
    bitset<169> ansPanel;
    // 使用 bitset 來做為 13 * 13 的面板
    unordered_map<bitset<169>, int> b2a; // bitset to ans
    // unordered_map<int, unordered_map<int, unordered_map<int, bitset<169>>>> btDb;
    int len;
    int ans;
    int height;
    int width;
    
    void backTrack(int x, int y, int n) {
        // 假如相同的面板已經出現過的話，看一下該次的表現，有沒有比以前出現過的時候還差。
        if(b2a.find(panel) == b2a.end()) {
            b2a[panel] = n;
        } else {
            if(b2a[panel] < n) {
                return;
            }
        }
        
        // 由大到小才不會 TLE
        // 藉由觀察，由大到小會更快收斂
        // --> 這個想法在面試的時候絕對會被電爆
        for(int i = len;i >= 1;i--) {
            // check bound           
            if(x + i > height) {
                continue;
            }
            if(y + i > width) {
                continue;
            }
            
            // new bitset
            bitset<169> newb (0);
            /* if(btDb.find(x) != btDb.end() &&
               btDb[x].find(y) != btDb[x].end() &&
               btDb[x][y].find(i) != btDb[x][y].end()) {
                newb = btDb[x][y][i];
            } else { */
                for(int j = 0;j < i;j++) {
                    for(int q = 0;q < i;q++) {
                        int index = (x + j) * 13 + (y + q);
                        newb[index] = true;
                    }
                }
                // btDb[x][y][i] = newb;
            // }
        
            // check overrlap    
            if((newb & panel).any()) {
                break;
            }
        
            // color
            panel |= newb;    
            
            // go to next point
            // 效能瓶頸很有可能在這裡
            if(panel == ansPanel) {
                ans = min(ans, n + 1);
            } else {
                
                if(y + i + 1 <= width && false == panel[(x * 13) + (y + i)]) {
                    // find the next x, y faster
                    backTrack(x, y + i, n + 1);    
                } else { 
                    bool f = false;
                    for(int j = 0;j < height;j++) {
                        for(int q = 0;q < width;q++) {
                            int index = j * 13 + q;
                            if(!panel[index]) {
                                backTrack(j, q, n + 1);
                                f = true;
                                break;
                            }
                        }
                        if(f) {
                            break;
                        }
                    }
                }
            }
            
            // un-color
            panel &= newb.flip();
        }
        
    }
    
public:
    int tilingRectangle(int n, int m) {
        if(n == m) {
            return 1;
        }
        
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                int index = i * 13 + j;
                ansPanel[index] = true;
            }
        }
        
        ans = INT_MAX;
        len = min(n, m);
        height = n;
        width = m;
                
        backTrack(0, 0, 0);
        
        return ans;
    }
};

LeetCode 473. Matchsticks to Square

想了很多天，結果差一行排序...完全想不到要這樣做 QQ

// 全部的火柴都要用到 !
#define um unordered_map
class Solution {
    vector<int> edges;
public:
bool backTrack(int index, int unit, vector<int> &st) {
        if(st.size() == index) {
            return true;
        }
        if(0 == index) {
            edges[0] += st[index];
            if(edges[0] <= unit) {
                bool res = backTrack(index + 1, unit, st);
                if(res) {
                    return true;
                }
            }
        } else {
            for(int i = 0;i < 4;i++) {
                if(edges[i] + st[index] <= unit) {
                    edges[i] += st[index];
                    
                    bool res = backTrack(index + 1, unit, st);
                    if(res) {
                        return true;
                    } 
                    
                    edges[i] -= st[index];
                }
            }
        }
        
        return false;
    }
    
    bool makesquare(vector<int>& matchsticks) {
        
        // 解答的神來一筆
        // 沒有這一行，會不停地 TLE
        // 從比較長的火柴開始排，可以更快地排除火柴過長的情況
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
                
        if(matchsticks.size() < 4) {
            return false;
        }
        
        int sum = 0;
        int unit;
        for(int i = 0;i < matchsticks.size();i++) {
            sum += matchsticks[i];
        }
        
        if(sum % 4 != 0) {
            return false;
        }
        
        unit = sum / 4;
        edges = vector<int>(4, 0);
        
        return backTrack(0, unit, matchsticks);
    }
};

LeetCode 90. Subsets II

// TODO : 看有沒有不用 map 去紀錄的作法
class Solution {
public:
    void dfs(int index, vector<int> &nums, vector<int> &v, vector<bool> &visited, map<vector<int>, bool> &mv, vector<vector<int>> &ans) {
        
        if(mv.find(v) == mv.end()) {
            mv[v];
            ans.push_back(v);
        } else {
            return;
        }
        
        for(int i = index;i < nums.size();i++) {
            if(!visited[i]) {
                visited[i] = true;
                
                v.push_back(nums[i]);
                dfs(i + 1, nums, v, visited, mv, ans);
                v.pop_back();
                
                visited[i] = false;
            }
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        
        map<vector<int>, bool> mv;
        vector<bool> visited = vector<bool>(nums.size(), false);
        vector<int> v;
        
        sort(nums.begin(), nums.end());
        
        dfs(0, nums, v, visited, mv, ans);
        
        // sort(ans.begin(), ans.end());
        
        return ans;
    }
};

LeetCode : 491. Increasing Subsequences

// backtracking
// TODO : 好奇有沒有不需要使用 map 來去除重複的方法
class Solution {
    
public:
    
    void backTrack(int index, vector<int> &tmp, vector<bool> &visited, map<vector<int>, bool> &m, vector<vector<int>> &ans, vector<int> &nums) {
        if(tmp.size() >= 2 && m.find(tmp) == m.end()) {
            m[tmp] = true;
            ans.push_back(tmp);
        }
        
        for(int i = index + 1;i < nums.size();i++) {
            if(nums[i] >= nums[index]) {
                visited[i] = true;
                tmp.push_back(nums[i]);
                backTrack(i, tmp, visited, m, ans, nums);
                tmp.pop_back();
                visited[i] = false;
            }
        }
    }
    
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool> visited = vector<bool> (nums.size(), false);
        map<vector<int>, bool> m;
        
        vector<int> tmp;
        for(int i = 0;i < nums.size();i++) {
            visited[i] = true;
            tmp.push_back(nums[i]);
            backTrack(i, tmp, visited, m, ans, nums);
            tmp.pop_back();
            visited[i] = false;
        }
        
        
        return ans;
    }
};

LeetCode : 2305. Fair Distribution of Cookies

// TODO : 效能太差了
class Solution {
    
private:
    int ans = INT_MAX;
    
public:
    
    int calcScore(vector<int> &tmp, vector<int> &cookies, int k) {
        vector<int> tv = vector<int>(k, 0);
        int maxVal = INT_MIN;
        for(int i = 0;i < tmp.size();i++) {
            tv[tmp[i]] += cookies[i];
        }
        
        for(int i = 0;i < tv.size();i++) {
            maxVal = max(maxVal, tv[i]);
        }
         
        return maxVal;
    }
    
    void backTrack(int n, vector<int> &tmp, vector<int> &cookies, int k) {
        // 假如餅乾分完了，就可以開始結算
        if(n == cookies.size()) {
            ans = min(ans, calcScore(tmp, cookies, k));
            return;
        }
        
        
        // 假如剩下的餅乾不夠分給大家
        // 就直接 return
        vector<int> tk = vector<int>(k, 0);
        int vk = k;
        for(int i = 0;i < tmp.size();i++) {
            if(tk[tmp[i]] == 0) {
                vk--;
            }
            tk[tmp[i]]++;
        }
        if(cookies.size() - n < vk) {
            return;
        }
        
        
        for(int i = 0;i < k;i++) {
            tmp.push_back(i);
            backTrack(n + 1, tmp, cookies, k);
            tmp.pop_back();
        }
        
    }
    
    int distributeCookies(vector<int>& cookies, int k) {
        int i = ans;
        vector<int> tmp;
        backTrack(0, tmp, cookies, k);
        return ans;
    }
};

LeetCode : 2375. Construct Smallest Number From DI String

// TODO : 試試看 greedy 的解法
class Solution {
public:
    
    string ans;
    
    bool dfs(int index, int stIndex, string &pat, vector<bool> &visited, vector<int> &tmp) {
        
        if(pat.size() == stIndex) {
            for(int i = 0;i < tmp.size();i++) {
                ans.push_back('0' + tmp[i]);
            }
            return true;
        }
        
        if('I' == pat[stIndex]) {
            for(int i = index + 1;i <= 9;i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    tmp.push_back(i);
                    if(dfs(i, stIndex + 1, pat, visited, tmp)) {
                        return true;
                    }
                    tmp.pop_back();
                    visited[i] = false;
                }
            }
        } else {
            for(int i = index - 1;i >= 1;i--) {
                if(!visited[i]) {
                    visited[i] = true;
                    tmp.push_back(i);
                    if(dfs(i, stIndex + 1, pat, visited, tmp)) {
                        return true;
                    }
                    tmp.pop_back();
                    visited[i] = false;
                }
            }
        }
        
        return false;
    }
    
    string smallestNumber(string pattern) {        
        vector<bool> visited(10, false);
        vector<int> tmp;
        
        for(int i = 1;i <= 9;i++) {
            tmp.push_back(i);
            visited[i] = true;
            if(dfs(i, 0, pattern, visited, tmp)) {
                break;
            }
            visited[i] = false;
            tmp.pop_back();
        }
                
        return ans;
    }
};

LeetCode : 1774. Closest Dessert Cost

// TODO : 效能太差，試試看 DP 解
// brute force
class Solution {
public:
    
    void dfs(int nowi, int *nowv, vector<int>& toppingCosts, vector<int> &t) {
        if(nowi == toppingCosts.size()) {
            t.push_back(*nowv);
            return;
        }
        
        for(int i = 0;i <= 2;i++) {
            *nowv += toppingCosts[nowi] * i;
            dfs(nowi + 1, nowv, toppingCosts, t);
            *nowv -= toppingCosts[nowi] * i;
        }
    }
    
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        
        // table;
        vector<int> t;
        
        int nowv = 0;
        for(int i = 0;i < baseCosts.size();i++) {
            nowv += baseCosts[i];
            dfs(0, &nowv, toppingCosts, t);
            nowv -= baseCosts[i];
        }
        
        // now target
        int nowt;
        // now diff
        int nowd = INT_MAX;
        
        for(int i = 0;i < t.size();i++) {
            int diff = abs(t[i] - target);
            if(diff < nowd) {
                nowd = diff;
                nowt = t[i];
            } else if(diff == nowd &&
                      t[i] < nowt) {
                nowt = t[i];
            }
        }
        return nowt;
    }
};

LeetCode : 320. Generalized Abbreviation

// back tracking
class Solution {
public:
    
    void backTrack(int nowi, string &tmp, vector<string> &ans, string &word) {
        
        if(nowi >= word.size()) {
            ans.push_back(tmp);
            return;
        }
                
        if(!(nowi > 0 && 
           tmp.back() >= '0' &&
           tmp.back() <= '9')) {
            int len = word.size() - nowi;
            for(int i = len;i >= 1;i--) {
                string s = to_string(i);
                tmp += s;
                backTrack(nowi + i, tmp, ans, word);
                for(int j = 0;j < s.size();j++) {
                    tmp.pop_back();
                }
            }
        }
        
        tmp.push_back(word[nowi]);
        backTrack(nowi + 1, tmp, ans, word);
        tmp.pop_back();
    }
    
    vector<string> generateAbbreviations(string word) {
        vector<string> ans;
        string tmp;
        backTrack(0, tmp, ans, word);   
        return ans;
    }
};

LeetCode : 1258. Synonymous Sentences

// TODO : erase 會出問題 ? why ?
class Solution {
public:
    
    void backTrack(int nowi, vector<string> &tokens, unordered_map<string, int> &st2int, unordered_map<int, vector<string>> &int2st, vector<string> &ans, string &tmp) {
        
        if(nowi == tokens.size()) {
            ans.push_back(tmp);
            return;
        }
        
        if(st2int.find(tokens[nowi]) == st2int.end()) {
            if(0 != nowi) {
                tmp.push_back(' ');
            }
            tmp += tokens[nowi];
            backTrack(nowi + 1, tokens, st2int, int2st, ans, tmp);
            if(0 != nowi) {
                tmp.pop_back();
            }
            for(int i = 0;i < tokens[nowi].size();i++) {
                tmp.pop_back();
            }
            return;
        }
        
        vector<string> &tmpv = int2st[st2int[tokens[nowi]]];
        for(int i = 0;i < tmpv.size();i++) {
            string &tmpst = tmpv[i];
            if(0 != nowi) {
                tmp.push_back(' ');
            }
            tmp += tmpst;
            backTrack(nowi + 1, tokens, st2int, int2st, ans, tmp);
            if(0 != nowi) {
                tmp.pop_back();
            }
            for(int j = 0;j < tmpst.size();j++) {
                tmp.pop_back();
            }
        }
    }
    
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        vector<string> ans;
        
        int nowi = 0;
        unordered_map<string, int> st2int;
        unordered_map<int, vector<string>> int2st;
        
        for(int i = 0;i < synonyms.size();i++) {
            int i1 = -1;
            int i2 = -1;
            
            if(st2int.find(synonyms[i][0]) != st2int.end()) {
                i1 = st2int[synonyms[i][0]];
            }
            
            if(st2int.find(synonyms[i][1]) != st2int.end()) {
                i2 = st2int[synonyms[i][1]];
            }
            
            if(-1 == i1 &&
               -1 == i2) {
                i1 = nowi;
                i2 = nowi;
                nowi++;
                
                if(st2int.find(synonyms[i][0]) == st2int.end()) {
                    st2int[synonyms[i][0]] = i1;
                    int2st[i1].push_back(synonyms[i][0]);
                }
            
                if(st2int.find(synonyms[i][1]) == st2int.end()) {
                    st2int[synonyms[i][1]] = i2;
                    int2st[i2].push_back(synonyms[i][1]);
                }
            } else if(-1 == i1) {
                i1 = i2;
                if(st2int.find(synonyms[i][0]) == st2int.end()) {
                    st2int[synonyms[i][0]] = i1;
                    int2st[i1].push_back(synonyms[i][0]);
                }
            } else if(-1 == i2) {
                i2 = i1;
                if(st2int.find(synonyms[i][1]) == st2int.end()) {
                    st2int[synonyms[i][1]] = i2;
                    int2st[i2].push_back(synonyms[i][1]);
                }
            } else {
                vector<string> &stv1 = int2st[i1];
                vector<string> &stv2 = int2st[i2];
                if(stv1.size() > stv2.size()) {
                    for(int i = 0;i < stv2.size();i++) {
                        st2int[stv2[i]] = i1;
                        int2st[i1].push_back(stv2[i]);
                        //不知道為什麼，這裡 erase 會出問題 ( access violation )
                        //int2st.erase(i2);                      
                    }
                } else {
                    for(int i = 0;i < stv1.size();i++) {
                        st2int[stv1[i]] = i2;
                        int2st[i2].push_back(stv1[i]);
                        //不知道為什麼，這裡 erase 會出問題 ( access violation )
                        //int2st.erase(i1);                      
                    }
                }
            }
            
        }
        
        for(int i = 0;i < nowi;i++) {
            vector<string> &tmpst = int2st[i];
            sort(tmpst.begin(), tmpst.end());
        }
        
        vector<string> tokens;
        string tmpst;
        // tokenize
        for(int i = 0;i < text.size();i++) {
            if(' ' != text[i]) {
                tmpst.push_back(text[i]);
            } else {
                tokens.push_back(tmpst);
                tmpst.clear();
            }
        }
        tokens.push_back(tmpst);
        
        tmpst.clear();
        backTrack(0, tokens, st2int, int2st, ans, tmpst);
        
        return ans;
    }
};

LeetCode : 1255. Maximum Score Words Formed by Letters

// G : 有點像 0-1 背包？
// --> 應該不是
// G : 因為 input 值域很小，所以可以 backtracking?
// 原本以為 word 可以重複選，結果不行... 這樣簡單多了
class Solution {
public:
    int maxVal = INT_MIN;
    void backTrack(int nowi, int nowv, vector<string>& words, vector<int>& le, vector<int>& score) {
        maxVal = max(maxVal, nowv);
        if(nowi >= words.size()) {
            return;
        }
        
        backTrack(nowi + 1, nowv, words, le, score);

        int j = 0;
        bool overflow = false;
        for(j = 0;j < words[nowi].size();j++) {
            // char index --> ci
            int ci = words[nowi][j] - 'a';
            le[ci]--;
            nowv += score[ci];
            if (le[ci] < 0) {
                overflow = true;
                break;                    
            }
        }
            
        if(overflow) {
            for(;j >= 0;j--) {
                int ci = words[nowi][j] - 'a';
                le[ci]++;
                nowv -= score[ci];
            }
        } else {
            backTrack(nowi + 1, nowv, words, le, score);
            for(j = 0;j < words[nowi].size();j++) {
                int ci = words[nowi][j] - 'a';
                le[ci]++;
                nowv -= score[ci];
            }
        }        
    }

    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<vector<int>> wordle = vector<vector<int>>(words.size(), vector<int>(26, 0));
        vector<int> le = vector<int>(26, 0);
        for(int i = 0;i < letters.size();i++) {
            le[letters[i] - 'a']++;
        }
        backTrack(0, 0, words, le, score);
        return maxVal;
    }
};

LeetCode : 1088. Confusing Number II

// back-tracking
class Solution {
public:
    int ans = 0;
    vector<int> num = {0, 1, 6, 8, 9};
    vector<int> num_r;
    bool valid(int n) {
        int ori_n = n;
        int rev_n = 0;

        while(n > 0) {
            rev_n *= 10;
            rev_n += num_r[n % 10];
            n /= 10;
        }

        return rev_n != ori_n;
    }
    void back_track(int now, int depth, int depth_limit, int value_limit) {
        if(depth == depth_limit) {
            if(now <= value_limit &&
               valid(now)) {
                ans++;
            }
            return;
        }

        for(int i = 0;i < num.size();i++) {
            now *= 10;
            now += num[i];
            back_track(now, depth + 1, depth_limit, value_limit);
            now /= 10;
        }      
    }

    int confusingNumberII(int n) {
        int len = 0;
        int ori_n = n;
        while(n > 0) {
            n /= 10;
            len++;
        }

        if (len == 10) {
            len -= 1;
            ans++;
        }

        num_r = vector<int>(10, 0);
        num_r[0] = 0;
        num_r[1] = 1;
        num_r[6] = 9;
        num_r[8] = 8;
        num_r[9] = 6;
        
        back_track(0, 0, len, ori_n);

        return ans;      
    }
};