408算法题leetcode--第30天
40. 组合总和 II
题目地址:40. 组合总和 II - 力扣(LeetCode)
题解思路:回溯
时间复杂度:O(n * 2n),n个数,每个数考虑选or不选(2n)
空间复杂度:O(n)
代码:
class Solution {
public:
vector<vector<int>>ret;
vector<int>arr;
void backtrack(vector<int>& candidates, int target, int sum, int start){
if(sum > target){
return ;
}
if(sum == target){
ret.push_back(arr);
return ;
}
int size = candidates.size();
for(int i = start; i < size; i++){
// 要对同一树层使用过的元素进行跳过
// 有序数组,从start开始的相同元素是同一分支的
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
arr.push_back(candidates[i]);
backtrack(candidates, target, sum + candidates[i], i + 1);
arr.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtrack(candidates, target, 0, 0);
return ret;
}
};
131. 分割回文串
题目地址:131. 分割回文串 - 力扣(LeetCode)
题解思路:如注释
时间复杂度:O(n * 2n),n个数,每个数考虑选or不选(2n)
空间复杂度:O(n^2)
代码:
class Solution {
public:
vector<vector<string>>ret;
vector<string>arr;
bool isPalindrome(string& str, int start, int end){
for(int i = start, j = end; i < j; i++, j--){
if(str[i] != str[j]){
return false;
}
}
return true;
}
void backtrack(string& s, int start){
if(start >= s.size()){
ret.push_back(arr);
return ;
}
int size = s.size();
for(int i = start; i < size; i++){
// 子串
if(isPalindrome(s, start, i)){
string str = s.substr(start, i - start + 1);
arr.push_back(str);
backtrack(s, i + 1);
arr.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
// 回溯 + 判断回文串
backtrack(s, 0);
return ret;
}
};