回溯算法LeetCode216組合求和3

問題描述

思路分析

首先确定這是一個什麼問題，很明顯，輸出的結果不需要考慮順序，那就是一個組合問題，組合問題的start并不總是從0開始，會随着遞歸的推進而改變，注意的事項就是這麼多。然後根據樹狀圖來解就行了。

代碼

class Solution {
    vector <vector <int> > res;
    void getCombunation(int start,int k,int n,vector <int> &p)
    {
        if(n==0&&k==0) {
            res.push_back(p);
            return;
        }
        if(n<0||k<0) return;
        for(int i=start;i<=9;i++) {
            p.push_back(i);
            getCombunation(i+1,k-1,n-i,p);
            p.pop_back();//回溯
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        if(n<=0||k<=0) return res;
        vector <int> p;
        getCombunation(1,k,n,p);
        return res;
    }
};