回溯+组合+代码随想录
思路:没想到直接做对了,在77-组合的基础上稍加变化,多了一个判断条件sum,整体还是代码随想录回溯的思想。
1)确定纵轴长度为k。
2)确定横轴小for长度为9。
3)确定结束条件为com.size() == k,同时当sum == n时摘果子。
代码注释:
1、2:sum跟着push和pop走。
3:可剪枝,com.size() == k时结束,但有时候甚至不需要到k,比如[1,2,4]=8,那么当遍历[1,7]直接为8的时候,
后面就可直接剪枝了。
4:可剪枝,i <= 9经典小for剪枝。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtrack(k, n, 1);
return coms;
}
private:
void backtrack(int k, int n, int idx) {
if (com.size() == k) { // wyh 3
if (sum == n) {
coms.push_back(com);
}
return;
}
for (int i = idx; i <= 9; i++) { // wyh 4
com.push_back(i);
sum += i; // wyh 1
backtrack(k, n, i + 1);
com.pop_back();
sum -= i; // wyh 2
}
}
vector<vector<int>> coms;
vector<int> com;
int sum = 0;
};
// 复习时,正常想到的思路
/*
* @lc app=leetcode.cn id=216 lang=cpp
*
* [216] 组合总和 III
*/
// @lc code=start
class Solution {
public:
bool isValid(vector<int>& com, int target) {
int sum = 0;
// 下面索引start的问题解决,此处就不需要
// set<int> com_set(com.begin(), com.end());
// if (com_set.size() != com.size()) {
// return false;
// }
// 这里会超时,应将sum放入每层递归中去计算
for (auto &c : com) {
sum += c;
}
return target == sum;
}
void combinationSum3(vector<vector<int>>& coms, vector<int>& com, int k, int n, int start) {
if (com.size() == k && isValid(com, n)) {
coms.push_back(com);
return;
}
// i<9而非i<n,因为i只能1-9,否则如果n>=10就会出问题
for (int i = start; i < 9; i++) {
com.push_back(i);
// 犯过两次错了,这里应该是i+1,而非start+1
// combinationSum3(coms, com, k, n, start + 1);
combinationSum3(coms, com, k, n, i + 1);
com.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> coms;
vector<int> com;
combinationSum3(coms, com, k, n, 1);
return coms;
}
};
// @lc code=end