易点科技_怀化平台_旺道seo优化软件_国外黄冈网站推广软件

40. 组合总和 II

题目地址：40. 组合总和 II - 力扣（LeetCode）

题解思路：回溯

时间复杂度：O(n * 2^{n)，n个数，每个数考虑选or不选（2}n）

空间复杂度：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 * 2^{n)，n个数，每个数考虑选or不选（2}n）

空间复杂度：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;}
};