# 140. Word Break II

Difficulty: Hard

Frequency: N/A

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = `"catsanddog"`,
dict = `["cat", "cats", "and", "sand", "dog"]`.

A solution is `["cats and dog", "cat sand dog"]`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
private:
unordered_map<string, vector<string>> m;
vector<string> combine(string word, vector<string> prev) {
for (int i = 0; i < prev.size(); i++) prev[i] += " " + word;
return prev;
}
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if (m.count(s)) return m[s];
vector<string> results;
if (wordDict.count(s)) results.push_back(s);
for (int i = 1; i < s.size(); i++) {
string word = s.substr(i);
if (wordDict.count(word)) {
string rem = s.substr(0, i);
vector<string> prev = combine(word, wordBreak(rem, wordDict));
results.insert(results.end(), prev.begin(), prev.end());
}
}
m[s] = results;
return results;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 254. (Locked)Factor Combinations

Difficulty:  Medium

Frequency: N/A

Numbers can be regarded as product of its factors. For example,

```8 = 2 x 2 x 2;
= 2 x 4.
```

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

1. Each combination’s factors must be sorted ascending, for example: The factors of 2 and 6 is `[2, 6]`, not `[6, 2]`.
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples:
input: `1`
output:

```[]
```

input: `37`
output:

```[]
```

input: `12`
output:

```[
[2, 6],
[2, 2, 3],
[3, 4]
]
```

input: `32`
output:

```[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<vector<int> > getFactors(int n) {
vector<vector<int> > results;
vector<int> tmp;
helper(n, tmp, results);
return results;
}

void helper(int n, vector<int> tmp, vector<vector<int> > &results) {
int i = tmp.empty() ? 2 : tmp.back();
for (; i <= n / i; i++) {
if (n % i == 0) {
tmp.push_back(i);
tmp.push_back(n / i);
results.push_back(tmp);
tmp.pop_back();
helper(n / i, tmp, results);
tmp.pop_back();
}
}
}
};

```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 079. Word Search

Difficulty: Medium

Frequency: N/A

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

```[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
```

word = `"ABCCED"`, -> returns `true`,
word = `"SEE"`, -> returns `true`,
word = `"ABCB"`, -> returns `false`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false;
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
for (int row = 0; row < board.size(); row++) {
for (int column = 0; column < board[row].size(); column++) {
if (findWord(word, 0, board, visited, row, column)) return true;
}
}
return false;
}
bool findWord(string &word, int idx, vector<vector<char>> &board, vector<vector<bool>> &visited, int row, int column) {
if (idx == word.size()) return true;
if (row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return false;
if (!visited[row][column] && board[row][column] == word[idx]) {
visited[row][column] = true;
if (findWord(word, idx + 1, board, visited, row - 1, column)) return true;
if (findWord(word, idx + 1, board, visited, row + 1, column)) return true;
if (findWord(word, idx + 1, board, visited, row, column - 1)) return true;
if (findWord(word, idx + 1, board, visited, row, column + 1)) return true;
visited[row][column] = false;
}
return false;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. If TLE, try to use reference as parameter.

Difficulty: Medium

Frequency: N/A

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given `"25525511135"`,

return `["255.255.11.135", "255.255.111.35"]`. (Order does not matter)

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<string> results;
vector<string> tmp;
helper(0, 0, s, tmp, results);
return results;
}

void helper(int part_num, int start_idx, string s, vector<string> tmp, vector<string> &results) {
if (part_num == 4 && start_idx == s.size()) {
string result;
for (int i = 0; i < tmp.size(); i++) result = result + tmp[i] + ".";
results.push_back(result.substr(0, result.size() - 1));
return;
}
if (((s.size() - start_idx) > (4 - part_num) * 3) || ((s.size() - start_idx) < (4 - part_num))) return;
for (int idx = start_idx; idx < start_idx + 3; idx++) {
if (valid(s.substr(start_idx, idx - start_idx + 1))) {
tmp.push_back(s.substr(start_idx, idx - start_idx + 1));
helper(part_num + 1, idx + 1, s, tmp, results);
tmp.pop_back();
}
}

}

bool valid(string s) {
if (s.size() > 3) return false;
else if (s.size() > 1 && s[0] == '0') return false;
else {
int num = 0;
for (int i = 0; i < s.size(); i++) {
num = num + (s[i] - '0') * pow(10, s.size() - i - 1);
}
if (num > 255) return false;
}
return true;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 037. Sudoku Solver

Difficulty: Hard

Frequency: N/A

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character `'.'`.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
helper(board, 0);
}
bool helper(vector<vector<char>> &board, int idx) {
if (idx == 81) return true;
int row = idx / 9;
int column = idx % 9;
if (board[row][column] != '.') {
return helper(board, idx + 1);
} else {
for (char c = '1'; c <= '9'; c++) {
if (isValid(row, column, c, board)) {
board[row][column] = c;
if (helper(board, idx + 1)) return true;
else board[row][column] = '.';
}
}
return false;
}
}
bool isValid(int row, int column, char num, vector<vector<char>> &board) {
int size = board.size();
for (int i = 0; i < size; i++) {
if (board[row][i] == num) return false;
}
for (int i = 0; i < size; i++) {
if (board[i][column] == num) return false;
}
for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
for (int j = column / 3 * 3; j < column / 3 * 3 + 3; j++) {
if (board[i][j] == num) return false;
}
}
return true;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Need to handle backing out the backtracking early.

# 060. Permutation Sequence

Difficulty: Medium

Frequency: N/A

The set `[1,2,3,…,n]` contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"321"`

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
string getPermutation(int n, int k) {
string result;
vector<int> fac(n, 1);
for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
vector<int> nums;
for (int i = 0; i < n; i++) nums.push_back(i + 1);
k--;
for (int i = n; i > 0; i--) {
int idx = k / fac[i - 1];
k = k % fac[i - 1];
result = result + to_string(nums[idx]);
nums.erase(nums.begin() + idx);
}
return result;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 131. Palindrome Partitioning

Difficulty: Medium

Frequency: N/A

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = `"aab"`,
Return

```  [
["aa","b"],
["a","a","b"]
]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> results;
vector<string> tmp;
helper(s, 0, tmp, results);
return results;
}
void helper(string s, int idx, vector<string> tmp, vector<vector<string>> &results) {
if (idx == s.size()) {
results.push_back(tmp);
return;
}
for (int i = idx; i < s.size(); i++) {
if (isPalindrome(s.substr(idx, i - idx + 1))) {
tmp.push_back(s.substr(idx, i - idx + 1));
helper(s, i + 1, tmp, results);
tmp.pop_back();
}
}
}
bool isPalindrome(string s) {
if (s.size() == 1) return true;
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
if (s[i] != s[j]) return false;
}
return true;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 052. N-Queens II

Difficulty: Hard

Frequency: N/A

Now, instead outputting board configurations, return the total number of distinct solutions.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int totalNQueens(int n) {
vector<string> tmp(n, string(n, '.'));
int total = 0;
helper(n, 0, tmp, total);
}
void helper(int n, int row, vector<string> tmp, int &total) {
if (row == n) {
total++;
return;
}
for (int column = 0; column < n; column++) {
if (isValid(tmp, row, column)) {
tmp[row][column] = 'Q';
helper(n, row + 1, tmp, total);
tmp[row][column] = '.';
}
}
}
bool isValid(vector<string> tmp, int row, int column) {
int size = tmp.size();
// Check if there is any queen in this column before
for (int i = 0; i < row; i++) {
if (tmp[i][column] == 'Q') return false;
}
// Check if there is any queen in 45° diagonal
for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
if (tmp[i][j] == 'Q') return false;
}
// Check if there is any queen in 135° diagonal
for (int i = row - 1, j = column + 1; i >= 0 && j < size; i--, j++) {
if (tmp[i][j] == 'Q') return false;
}
return true;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 051. N-Queens

Difficulty: Hard

Frequency: N/A

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

```[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> results;
vector<string> tmp(n, string(n, '.'));
helper(n, 0, tmp, results);
return results;
}
void helper(int n, int row, vector<string> tmp, vector<vector<string>> &results) {
if (row == n) {
results.push_back(tmp);
return;
}
for (int column = 0; column < n; column++) {
if (isValid(tmp, row, column)) {
tmp[row][column] = 'Q';
helper(n, row + 1, tmp, results);
tmp[row][column] = '.';
}
}
}
bool isValid(vector<string> tmp, int row, int column) {
int size = tmp.size();
// Check if there is any queen in this column before
for (int i = 0; i < row; i++) {
if (tmp[i][column] == 'Q') return false;
}
// Check if there is any queen in 45° diagonal
for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
if (tmp[i][j] == 'Q') return false;
}
// Check if there is any queen in 135° diagonal
for (int i = row - 1, j = column + 1; i >= 0 && j < size; i--, j++) {
if (tmp[i][j] == 'Q') return false;
}
return true;
}
};
```
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

# 216. Combination Sum III

Difficulty: Medium

Frequency: N/A

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

```[[1,2,4]]
```

Example 2:

Input: k = 3, n = 9

Output:

```[[1,2,6], [1,3,5], [2,3,4]]
```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> results;
vector<int> input = {1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int> tmp;
helper(input, tmp, k, n, 0, results);
return results;
}
void helper(vector<int> input, vector<int> tmp, int count, int target, int idx, vector<vector<int>> &results) {
if (tmp.size() == count) {
if (!target) results.push_back(tmp);
return;
}
for (int i = idx; i < input.size() && target >= input[i]; i++) {
tmp.push_back(input[i]);
helper(input, tmp, count, target - input[i], i + 1, results);
tmp.pop_back();
}
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: