Perhaps the simplest solution using recursion(backtracing).


  • 13
    E

    The idea is that C(n,k) = C(n-1, k-1) U n + C(n-1,k), do you get this?

    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            
            vector<vector<int> > result;
            if (n < 1 || k <1 || k > n)
            {
                return result;
            }
            
            result = combine(n-1, k-1);
            
            if(result.empty())
            {
                result.push_back(vector<int>{n});
            }
            else
            {
                for (vector<vector<int> >::iterator it = result.begin();
                        it!= result.end(); it++)
                {
                    it->push_back(n);
                }
            }
            vector<vector<int> > result2 = combine(n-1, k);
            result. insert(result.end(), result2.begin(), result2.end());
            
            return result;
        }
    };

  • 2
    J

    I don't want to copy the returned vectors every time, so I just flip coins:

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> result;
            if (n < 1 || k < 1 || k > n) return result;
            vector<int> v;
            collect(n, k, 0, v, result);
            return result;
        }
        void collect(int n, int k, int i, vector<int> &v, vector<vector<int>> &ret) {
            if (v.size() == k) {
                ret.push_back(v);
                return;
            }
            while (i < n) {
                v.push_back(i + 1);
                collect(n, k, i + 1, v, ret);
                v.pop_back();
                i++;
            }
        }
    };
    

  • 0
    S

    really quite simple


  • 0
    H

    That's indeed the DP solution. Very nice.


  • 0
    W

    "C(n,k) = C(n, 1) * C(n-1, k-1)" doesn't look right to me. I think it should be C(n,k) = C(n, 1) / k * C(n-1, k-1). The code is neat though, thx :-)


  • 0
    J

    Thanks, you are right. I've edited my answer. :)


  • 0
    N

    Can you explain your approach in detail ?

    Especially this part of code -

    if(result.empty())
            {
                result.push_back(vector<int>{n});
            }
            else
            {
                for (vector<vector<int> >::iterator it = result.begin();
                        it!= result.end(); it++)
                {
                    it->push_back(n);
                }
            }

Log in to reply
 

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