# Backtracking
# 17. Letter Combinations of a Phone Number
## Question (Medium)
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
## Solution (C++)
```c=
typedef map<char, vector<char>> mymap;
class Solution {
public:
void backtracking(mymap mapping, vector<string>& ans, string digits, int index, string current){
if(current.length() == digits.length()){
ans.push_back(current);
return;
}
for(int i=0; i<mapping[digits[index]].size(); i++){
backtracking(mapping, ans, digits, index+1, current+mapping[digits[index]][i]);
}
}
vector<string> letterCombinations(string digits) {
mymap mapping;
mapping['2'] = {'a', 'b', 'c'};
mapping['3'] = {'d', 'e', 'f'};
mapping['4'] = {'g', 'h', 'i'};
mapping['5'] = {'j', 'k', 'l'};
mapping['6'] = {'m', 'n', 'o'};
mapping['7'] = {'p', 'q', 'r', 's'};
mapping['8'] = {'t', 'u', 'v'};
mapping['9'] = {'w', 'x', 'y', 'z'};
vector<string> ans;
if(digits.length()==0)
return ans;
string current = "";
backtracking(mapping, ans, digits, 0, current);
for(int i=0; i<ans.size(); i++)
cout<<ans[i]<<endl;
return ans;
}
};
```
## Notes:
* 這題蠻簡單的，因為她是要**輸出所有可能的組合**而已。所以就brute force。
* 需先建立int->char的mapping關係
* 用backtracking的方式，遞迴找出所有可能組合。
---
# 78. Subsets
## Question (Medium)
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
## Solution (C++)
```c=
class Solution {
public:
void back_track(vector<int>& nums, vector<int> current, int start_idx, vector<vector<int>>& ans){
for(int i=start_idx; i<nums.size(); i++){
current.push_back(nums[i]);
ans.push_back(current);
back_track(nums, current, i+1, ans);
current.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> zero;
ans.push_back(zero);
for(int i=0; i<nums.size(); i++){
vector<int> temp;
temp.push_back(nums[i]);
ans.push_back(temp);
back_track(nums, temp, i+1, ans);
}
return ans;
}
};
```
## Notes
* 用recursive來解
* 用c++的call by reference的變數ans，來記錄每個subset。
---
# 39. Combination Sum
## Question (Medium)
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
## Solution (C++)
```c=
class Solution {
public:
void back_track(vector<int>& c, vector<int> current, int start_idx, int target, int s, vector<vector<int>>& ans){
if(s>target)
return;
if(s==target)
ans.push_back(current);
for(int i=start_idx; i<c.size(); i++){
current.push_back(c[i]);
back_track(c, current, i, target, s+c[i], ans);
current.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
for(int i=0; i<candidates.size(); i++){
vector<int> temp;
temp.push_back(candidates[i]);
back_track(candidates, temp, i, target, candidates[i], ans);
}
return ans;
}
};
```
## Notes:
* 用recursive來解
* 因為一個數字可以重複取，所以要特別注意這點。
* recursive時，要判斷當下的summation有沒有超過target。
---
# 46. Permutations
## Question (Medium)
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
## Solution (c++)
```c=
class Solution {
public:
void permutations(vector<int> nums, vector<int> current, vector<vector<int>>& ans){
if(nums.size()==0){
ans.push_back(current);
return;
}
for(int i=0; i<nums.size(); i++){
current.push_back(nums[i]);
vector<int> temp(nums);
temp.erase(temp.begin()+i, temp.begin()+i+1);
permutations(temp, current, ans);
current.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> current;
permutations(nums, current, ans);
return ans;
}
};
```
## Notes
* 此題為列出所有的排列。
* 使用recursize來解
* 用erase移除已經visited過的元素，接著就是遞迴處理所有可能的排列。
* 當nums的大小為0時，表示已找到一排列，將其存入ans裡面紀錄。
---
# 79. Word Search
## Question (Medium)
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
## Solution (C++)
```c=
class Solution {
public:
bool backtracking(vector<vector<char>>& board, int i, int j, int str_index, string word){
if(i<0 || j<0 || i>=board.size() || j>=board[0].size())
return false;
if(board[i][j] != word[str_index])
return false;
if(str_index == word.size()-1)
return true;
char temp = board[i][j];
board[i][j]='*';
//top down left right -> backtracking
bool ans = backtracking(board, i-1, j, str_index+1, word) ||
backtracking(board, i+1, j, str_index+1, word) ||
backtracking(board, i, j-1, str_index+1, word) ||
backtracking(board, i, j+1, str_index+1, word);
board[i][j] = temp;
return ans;
}
bool exist(vector<vector<char>>& board, string word) {
int r_size = board.size();
int c_size = board[0].size();
for(int i=0; i<r_size; i++){
for(int j=0; j<c_size; j++){
if(board[i][j] == word[0]){
if(backtracking(board, i, j, 0, word))
return true;
}
}
}
return false;
}
};
```
## Notes:
* 這題有個地方要注意，在寫recursive function的時候，參數盡量不要使用**call by value**的方式傳遞，原本的visit matrix太大，會導致運行的時候TLE。
* 將visit matrix換成line 11, line 17的用法，就不用額外建立visit matrix了。
---
# 113. Path Sum II
## Question (Medium)
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
## Solution (C++)
```c=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, vector<vector<int>>& record, vector<int>& temp, int current, int targetSum){
if(root==NULL)
return;
current+=root->val;
temp.push_back(root->val);
if(current == targetSum && root->left==NULL && root->right==NULL){
record.push_back(temp);
}
dfs(root->left, record, temp, current, targetSum);
dfs(root->right, record, temp, current, targetSum);
temp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> record;
vector<int> temp;
if(root==NULL)
return record;
dfs(root, record, temp, 0, targetSum);
return record;
}
};
```
## Notes:
* 簡單的dfs，只要在recursive的時候判斷是否等於targetSum即可。
* 要注意是要計算**root到leaf node的總和**，參考line 19 。
* 之前寫backtracking的題目都是使用call by value，現在發現call by reference比較好，且較省時間(**vector<int>& temp**)，只要在每次recursive完pop出來即可(line 24)。
---
# 77. Combinations
## Question(Medium)
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
## Solution(C++)
```c=
class Solution {
public:
void backtracking(vector<vector<int>>& ans, vector<int>& current, int index, int n, int k){
//index =1
if(current.size()==k){
ans.push_back(current);
return;
}
for(int i=index; i<=n; i++){
current.push_back(i);
backtracking(ans, current, i+1, n, k);
current.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
//C n取k
vector<vector<int>> ans;
vector<int> current;
backtracking(ans, current, 1, n, k);
return ans;
}
};
```
## Notes:
Sign in with Wallet
Connect another wallet