# 046. Permutations

Difficulty:

Frequency:

Given a collection of distinct numbers, return all possible permutations.

For example,
`[1,2,3]` have the following permutations:
`[1,2,3]`, `[1,3,2]`, `[2,1,3]`, `[2,3,1]`, `[3,1,2]`, and `[3,2,1]`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> results;
vector<int> tmp_vec;
permute_helper(nums, results, tmp_vec);
return results;
}
void permute_helper(vector<int> nums, vector<vector<int>> &results, vector<int> tmp_vec) {
if (nums.empty()) {
results.push_back(tmp_vec);
return;
}
for (int i = 0; i < nums.size(); i++) {
tmp_vec.push_back(nums[i]);
vector<int> new_nums = nums;
new_nums.erase(new_nums.begin() + i);
permute_helper(new_nums, results, tmp_vec);
tmp_vec.pop_back();
}
}
};
```

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

Things to learn:

# 320. (locked)Generalized Abbreviation

Difficulty: Medium

Frequency: N/A

Write a function to generate the generalized abbreviations of a word.
Example:
Given word = `"word"`, return the following list (order does not matter):
`["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]`

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
vector<string> generateAbbreviations(string word) {
vector<string> results;
string tmp;
helper(word, 0, tmp, results);
return results;
}
void helper(string word, int idx, string tmp, vector<string> &results) {
if (idx == word.size()) {
results.push_back(tmp);
return;
}
helper(word, idx + 1, tmp + word[idx], results);
for (int i = 1; i < word.size() - idx; i++)
helper(word, idx + 1 + i, tmp + to_string(i) + word[idx + 1], results);
helper(word, word.size(), tmp + to_string(word.size() - idx), results);
}
};

```

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

Things to learn:

# 294. (locked)Flip Game II

Difficulty: Medium

Frequency: N/A

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: `+` and `-`, you and your friend take turns to flip two consecutive `"++"` into `"--"`. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given `s = "++++"`, return true. The starting player can guarantee a win by flipping the middle `"++"` to become `"+--+"`.

My solution:
Data structure:
string, backtracking
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
bool canWin(string s) {
for (int i = -1; i = s.find("++", i + 1) >= 0; ) {
if(!canWin(s.substr(0, i) + "--" + s.substr(i + 2)))
return true;
}
return false;
}
}
```

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

Things to learn: