216 组合总和III
在77 组合基础上加了限制条件,不仅需要k个元素的组合,而且该组合之和为n
因此我们只需要加上限制即可,其余与77 组合做法一致
限制条件:
if(path.size() == k && n == 0)
class Solution {
private:
const int N = 9;
vector<vector<int>> ans;
vector<int> path;
void dfs(int k, int n, int startIndex){
// 注意这里需要判断n == 0以保证k个元素之和恰好为n
if(path.size() == k && n == 0){
ans.push_back(path);
return ;
}
for(int i = startIndex; i <= N - (k - path.size()) + 1; i++){
if(i <= n){
path.push_back(i);
// 记得这里要n - i,表示选择元素i后,剩余的元素和
dfs(k, n - i, i + 1);
path.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1);
return ans;
}
};