[数据结构与算法]力扣（77.216）补8.12

77.组合

简单组合问题，长时间不做，也忘了回溯模板了。。。

216.组合总和Ⅲ

这里是无论sum为多少，都先让path长为k，在长为k的条件下，如果sum为n则赋值再return，否则不管，直接return回溯。

不愧是回溯，即使有模板，也不是那么好理解（不好根据代码模拟一遍用例，容易晕）。

class Solution {

public:

? ? vector<vector<int>>ret;

? ? vector<int>path;

? ? ? ? ? ?void dfs(int k,int n,int sum,int start){

? ? ? ? ? ? if(path.size()==k){

? ? ? ? ? ? ? ? if(sum==n)

? ? ? ? ? ? ? ? ret.push_back(path);

? ? ? ? ? ? ? ? return;

? ? ? ? ? ? }

? ? ? ? ? ? for(int i=start;i<=9;i++){

? ? ? ? ? ? ? ? path.push_back(i);

? ? ? ? ? ? ? ? sum+=i;

? ? ? ? ? ? ? ? dfs(k,n,sum,i+1);

? ? ? ? ? ? ? ? path.pop_back();

? ? ? ? ? ? ? ? sum-=i;

? ? ? ? ? ? }

? ? ? ? }

? ? ?vector<vector<int>> combinationSum3(int k, int n) {

? ? ? ? ?dfs(k,n,0,1);

? ? ? ? ?return ret;? ? ? ??

? ? }

};

?