Share my easy recursive solution (c++ 0ms)


  • 0
    J
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int> > ret;
        recComb(1, k, n, ret);
        return ret;
    }
    
    void recComb(int start, int k, int T, vector<vector<int> > &res)
    {
        if (start > 9 || T < 0) return;
        if (k == 1)
        {
            if (T >= start && T <= 9)
            {
                vector<int> comb(1, T);
                res.push_back(comb);
            }
        }
        else
        {
            int subT = T - start;
            if (subT > 0) // start is selected
            {
                vector<vector<int> > subres;
                recComb(start+1, k-1, subT, subres);
                for (int i = 0; i < subres.size(); ++i)
                {
                    vector<int> comb(1, start);
                    comb.insert(comb.end(), subres[i].begin(), subres[i].end());
                    res.push_back(comb);
                }
            }
         
            recComb(start+1, k, T, res); // start is not selected
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.