C++ recursive solution inspired by combination equation C(n,k) = C(n-1,k-1)+C(n-1,k) detail explanation


  • 0

    Let C(n,k) be the number of combinations to choose k elements out of n elements. Then there are only two cases:

    • element n is chosen: so we only need to choose k-1 out of first n-1 and there are C(n-1,k-1) combinations.
    • element n is not chosen: so we need to choose k out of first n-1 and there are C(n-1,k) combinations.
      So we have equality C(n,k) = C(n-1,k-1)+C(n-1,k).
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> res;
            if (k == 1) { // base case
                for (int i = 1; i <= n; ++i) res.push_back({i});
                return res;
            } 
            else if (k == n) { // base case
                res.resize(1);
                for (int i = 1; i <= n; ++i) res[0].push_back(i);
                return res;
            }
            
            res = combine(n-1,k); // all combinations without n
            auto tmp = combine(n-1,k-1);
            for (auto& x:tmp) x.push_back(n); // all combinations with n
            res.insert(res.end(), tmp.begin(), tmp.end());
            return res;
        }
    

Log in to reply
 

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