跳转至

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;
    }
};