# Leetcode刷題學習筆記 -- Backtracking
## Introduction
[131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)
給你一個string找出所有可能的切割方法，讓切割出來的substring都是palindrome。例如: s = "aab"，則返回[["a","a","b"],["aa","b"]]
+ backtracking 可以視為queue裡面有每個可能的答案，
+ 最後條件滿足就把答案存起來，
+ pop掉最後一個，繼續從這個狀態尋找下一個可能
+ 從上面的答案可以知道，一開始我的candidate可能是"a"或是"aa"
+ 所以必須設計一個演算法可以找出candidate的可能性。
列舉所有的結果，利用recursive來拆解問題。
```cpp=
backtrace() {
if(滿足條件) {
儲存結果;
離開;
}
for(列舉所有可能) {
儲存新的可能;
backtrace();
撤銷新的可能;
}
}
```
### [131. Palindrome Partitioning(Medium)](https://leetcode.com/problems/palindrome-partitioning/)
給你一個string，回傳所有可以切割出來的回文組合。
> 1. 一個一個判斷字串是否為palindrome，如果是繼續判斷剩下的substring。
> 2. 當全部字串都判斷完了，就儲存結果。
> 3. 退掉前一個成功的結果，繼續往下處理。
```cpp=
bool isPalindrome(string s) {
auto n = s.length();
if(n == 0) return true;
else if(n == 1) return true;
else {
for(int i = 0; i < n / 2; ++i) {
if(s[i] != s[n - i - 1])
return false;
}
return true;
}
}
void helper(vector<vector<string>>& rtn, vector<string>& tmp, string s) {
if(s.length() == 0)
rtn.push_back(tmp);
// 每次增加一個char判斷是否為palindrome
for(int i = 1; i <= s.length(); ++i) {
// 如果是，則剩下的substring繼續判斷。
// 如果不是，則增加string的長度。
if(isPalindrome(s.substr(0, i))) {
tmp.push_back(s.substr(0, i));
helper(rtn, tmp, s.substr(i));
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> rtn;
vector<string> tmp;
helper(rtn, tmp, s);
return rtn;
}
```
### [79. Word Search(Medium)](https://leetcode.com/problems/word-search/)
給你一個vector<vector<char>>> board，找出board中有沒有string word。
> 1. 如果word.length() == 1，只要搜尋board中有沒有char和他一樣的。
> 2. 如果word.length() == 2，則找到(1)之後，還要繼續往四個方向尋找。必且必須符合, 1)沒有出界，2)沒有訪問過，3)字元一樣
> 3. 符合(2)則繼續往下找，直到idx == word.length()全部找完為止。
```cpp=
class Solution {
int n, m;
vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool inRange(int y, int x) {
return (x < 0 || y < 0 || y >= n || x >= m) ? false : true;
}
bool search(vector<vector<char>>& board, string word, int idx, int y, int x, vector<vector<bool>>& v) {
if(idx == word.length()) return true;
if(!inRange(y, x) || v[y][x] || board[y][x] != word[idx]) return false;
else {
v[y][x] = true;
bool res{false};
for(auto& dir : dirs)
// 四個方向的board[y][x]是否和word[idx + 1]一樣？
res |= search(board, word, idx + 1, y + dir[0], x + dir[1], v);
v[y][x] = false;
return res;
}
}
public:
bool exist(vector<vector<char>>& board, string word) {
n = board.size();
m = board[0].size();
vector<vector<bool>> v(n, vector<bool>(m));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
// board[i][j]和word[0]是否一樣
if(search(board, word, 0, i, j, v))
return true;
}
}
return false;
}
};
```
### [47. Permutations II](https://leetcode.com/problems/permutations-ii/)
給你一個vector<int> nums其中的數字有可能會重複，回傳所有不重複的排列。
> 參考leetcode給的解答
> 1. 因為數字有重複，所以先對數字做統計。
> 2. 以前的backtracking都是對vector，現在改對map。
```cpp
class Solution {
void helper(unordered_map<int, int>& m, vector<int>& cur, vector<vector<int>>& rtn, int sz) {
if(cur.size() == sz) {
rtn.push_back(cur);
return;
}
for(auto& item : m) {
if(item.second == 0) continue;
cur.push_back(item.first);
item.second--;
helper(m, cur, rtn, sz);
item.second++;
cur.pop_back();
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
int sz = nums.size();
unordered_map<int, int> m; // value, cnt
for(auto& n : nums) m[n]++;
vector<vector<int>> rtn;
vector<int> cur;
helper(m, cur, rtn, sz);
return rtn;
}
};
```
### [1066. Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/description/)
在2D平面上(XY座標)，有vector<vector<int>> workers和vector<vector<int>> bikes。每個worker必須分配一台bike，試找出最少的Manhattan distances的分配法。其中$Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|$
> 1. 一開始覺得要用Greedy，但是怎樣寫都有錯誤。
> 2. 最簡單的方法就是暴力解，每台bike(M)都有可能分配給worker(N)，所以有$M^N$的解法。
> 3. 這邊的暴力解就是使用backtracking，因為固定worker的順序，只要針對bike做排列即可。如下面的解法。
> 4. ==固定一個變數，就是worker會依序分配，然後遍歷剩下bike的所有可能性。==
> 4. 其中使用一個int來表示分配過的bike，因為題目給定bike最多只有10台。
```cpp=
class Solution {
int minans{INT_MAX};
int dist(vector<int>& w, vector<int>& b) {
return abs(w[0] - b[0]) + abs(w[1] - b[1]);
}
void dfs(vector<vector<int>>& w, vector<vector<int>>& b, int u, int idx, int cur) {
if(idx == w.size()) {
minans = min(minans, cur);
return;
}
for(int i = 0; i < b.size(); ++i) {
if((u & (1 << i)) == 0)
dfs(w, b, u | 1 << i, idx + 1, cur + dist(w[idx], b[i]));
}
}
public:
int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
dfs(workers, bikes, 0, 0, 0);
return minans;
}
};
```
> 5. 但是這種解法的time complexity不是很好，因為會有很多重複計算的過程。
> 6. 因為當mask一樣的時候，表示剩下的bikes是一樣的。workers是依序取的，所以表示剩下的worker也是一樣的。
例如:mask = 0011，表示index = 0, 1的腳踏車已經被取走
works = 0-->1, 或是 1-->0 順序不重要，剩下works = 2, 3
所以答案一樣，不用重新計算。
> 7. 所以我們可以用mask當成index來查詢是否有重複計算。
> 8. 這題可以當成是一個模板，所有用暴力解來分配的題目都可以這樣解。
```cpp=
class Solution {
int dist(vector<int>& w, vector<int>& b) {
return abs(w[0] - b[0]) + abs(w[1] - b[1]);
}
int dfs(vector<vector<int>>& w, vector<vector<int>>& b, int mask, int idx) {
if(idx == w.size()) return 0;
if(~mem[mask]) return mem[mask];
int minans{INT_MAX};
for(int i = 0; i < b.size(); ++i) {
if(!(mask & (1 << i)))
minans = min(minans, dfs(w, b, mask | 1 << i, idx + 1) + dist(w[idx], b[i]));
}
return mem[mask] = minans;
}
vector<int> mem;
public:
int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
mem.resize(pow(2, bikes.size()), -1);
return dfs(workers, bikes, 0, 0);
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
Connect another wallet