Dynamic Programming C++ solution.


  • 0
    C
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            if (n < k || n < 0 || k < 0) return vector<vector<int>>(); //undefined problem
            
            //dynamic programming cache
            vector<vector<int>> cache[n+1][n+1];
            
            vector<vector<int>> setOfEmptySet(1, vector<int>());
            //base cases
            for (int ni=0; ni<=n; ni++) {
                for (int ki=0; ki<=n; ki++) {
                    if (ni < ki) cache[ni][ki] = vector<vector<int>>(); //undefined problem
                    else if (ki == 0) cache[ni][ki] = setOfEmptySet;    //[]
                }
            }
            
            //dynamic programming loop
            for (int ni=1; ni<=n; ni++) {
                for (int ki=1; ki<=k; ki++) { //note; limit to ki<=k instead of ki<=ni because
                                              //we are only interested in nCk (and not beyond k)
                    int chosen = ni;
                    vector<vector<int>> recordDrop = cache[ni-1][ki];  //drop this number
                    vector<vector<int>> recordTake = cache[ni-1][ki-1];//take this number
                    for (vector<int>& rec : recordTake) {
                        rec.push_back(chosen);
                    }
                    recordDrop.insert(recordDrop.end(), recordTake.begin(), recordTake.end());
                    cache[ni][ki] = recordDrop;
                }
            }          
            return cache[n][k];
        }
    };

  • 0
    C

    Recurrence equation is:
    C (n, k) = (n U C(n-1, k-1) ) + (C(n-1, k))
    First case: Take the nth number, and choose k-1 from remaining n-1.
    Second case: Drop the nth number, and choose k from remaining n-1.


Log in to reply
 

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