代码随想录day27

39. 组合总和

 1 // 版本一
 2 class Solution {
 3 private:
 4     vector<vector<int>> result;
 5     vector<int> path;
 6     void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
 7         if (sum > target) {
 8             return;
 9         }
10         if (sum == target) {
11             result.push_back(path);
12             return;
13         }
14 
15         for (int i = startIndex; i < candidates.size(); i++) {
16             sum += candidates[i];
17             path.push_back(candidates[i]);
18             backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
19             sum -= candidates[i];
20             path.pop_back();
21         }
22     }
23 public:
24     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
25         result.clear();
26         path.clear();
27         backtracking(candidates, target, 0, 0);
28         return result;
29     }
30 };

40. 组合总和 II

 1 class Solution {
 2 private:
 3     //1、确定回溯函数的参数和返回值
 4     vector<vector<int>> result;
 5     vector<int> path;
 6     void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
 7         if (sum > target) {
 8             return;
 9         }
10         //2、确定回溯的结束条件
11         if (sum == target) {
12             result.push_back(path);
13             return;
14         }
15         //3、确定回溯的单层逻辑
16         for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
17             //要对同一树层使用过的元素进行跳过 这个去重逻辑值得学习
18             if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
19                 continue;
20             }
21             path.push_back(candidates[i]);
22             sum += candidates[i];
23             used[i] = true;
24             backtracking(candidates, target, sum, i + 1, used);
25             used[i] = false;
26             sum -= candidates[i];
27             path.pop_back();
28         }
29         return;
30     }
31 public:
32     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
33         vector<bool> used(candidates.size(), false);
34         result.clear();
35         path.clear();
36         //首先把candidates进行排序
37         sort(candidates.begin(), candidates.end());
38         backtracking(candidates, target, 0 , 0, used);
39         return result;
40     }
41 };

131. 分割回文串

c++ substr()的用法：

 代码如下：

 1 class Solution {
 2 private:
 3     vector<vector<string>> result;
 4     vector<string> path;
 5     void backtracking(const string& s, int startIndex) {
 6         if (startIndex >= s.size()) {
 7             result.push_back(path);
 8             return;
 9         }
10         for ( int i = startIndex; i < s.size(); i++) {
11            if (isPalindrome(s, startIndex, i)) {
12                //分割字符串
13                string str = s.substr(startIndex, i - startIndex + 1);
14                path.push_back(str);
15            } else {
16                continue;
17            }
18            backtracking(s, i + 1);
19            path.pop_back();
20         }
21     }
22     //判断截取出的字符串是否为回文字符串
23     bool isPalindrome(const string& s, int start, int end) {
24         for (int i = start, j = end; i < j; i++, j--) {
25             if (s[i] != s[j]) {
26                 return false;
27             }
28         }
29         return true;
30     }
31 public:
32     vector<vector<string>> partition(string s) {
33         result.clear();
34         path.clear();
35         backtracking(s, 0);
36         return result;
37     }
38 };