一、题意
二、解答过程
这道题和 《77.组合》比起来,就是多了一些限制条件,本题是要找到和为n的k个数的组合,而整个集合已经是固定的了[1,…9]
图中可以看出,只有取集合红色的是满足条件的。
- 回溯三部曲
class Solution { private: vector<vector<int>>result;//存放结果集 vector<int> path;//符合条件的结果 // targetSum:目标和,也就是题目中的n。 // k:题目中要求k个数的集合。 // sum:已经收集的元素的总和,也就是path里元素的总和。 // startIndex:下一层for循环搜索的起始位置。 void backtracking(int targetSum,int k,int sum,int startIndex) { if (sum > targetSum) { // 剪枝操作:如果元素和大于后面的数值,后面就不用遍历了 return; // 如果path.size() == k 但sum != targetSum 直接返回 } if(path.size()==k) { if(sum==targetSum) { result.push_back(path); } return; } for(int i=startIndex;i<=9;i++) { sum+=i;//处理 path.push_back(i);//处理 backtracking(targetSum,k,sum,i+1); sum-=i;//回溯 path.pop_back();//回溯 } } public: vector<vector<int>> combinationSum3(int k, int n) { result.clear();//可以不加这行代码 path.clear();//可以不加这行代码 backtracking(n,k,0,1); return result; } };