增量构造答案的过程 用递归解决
回溯三问
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<string> number_string = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
string cur;
void dfs(string digits, int x){
if(x >= digits.size()){
if(cur != "")
ans.push_back(cur);
return;
}
int index = digits[x] - '0';
cout << index << endl;
for(int i = 0; i < number_string[index - 1].size(); ++ i){
cur.push_back(number_string[index - 1][i]);
dfs(digits, x + 1);
cur.pop_back();
}
}
vector<string> letterCombinations(string digits) {
dfs(digits, 0);
return ans;
}
};
|
子集型回溯
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<vector<int>> ans;
vector<int> cur;
void dfs(vector<int>& nums, int index){
ans.push_back(cur);
if(index == nums.size()){
return;
}
for(int i = index; i < nums.size(); ++ i){
cur.push_back(nums[i]);
dfs(nums, i + 1);
cur.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
dfs(nums, 0);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<vector<int>> ans;
vector<int> cur;
void dfs(vector<int>& nums, int index){
if(index == nums.size()){
ans.push_back(cur);
return;
}
cur.push_back(nums[index]);
dfs(nums, index + 1);
cur.pop_back();
dfs(nums, index + 1);
}
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
cur.push_back(nums[0]);
dfs(nums, 1);
cur.pop_back();
dfs(nums, 1);
return ans;
}
};
|
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
分割字符串，先决定是否分割，如果要分割，检查当前是不是回文的，如果是，继续分割，如果不是，不分割。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
bool is_huiwen(string s, int left, int right){
while (left < right)
if (s[left++] != s[right--])
return false;
return true;
}
vector<vector<string>> ans;
vector<string> cur;
void dfs(string s, int index, int start){
if(s.size() == index){
ans.push_back(cur);
return;
}
if (index < s.size() - 1)
dfs(s, index + 1, start);
if(is_huiwen(s, start, index)){
cur.push_back(s.substr(start, index - start + 1));
dfs(s, index + 1, index + 1);
cur.pop_back();
}
}
vector<vector<string>> partition(string s) {
dfs(s, 0, 0);
return ans;
}
};
|
