A short recursive Java solution based on C(n,k)=C(n-1,k-1)+C(n-1,k)


  • 81
    K

    Basically, this solution follows the idea of the mathematical formula C(n,k)=C(n-1,k-1)+C(n-1,k).

    Here C(n,k) is divided into two situations. Situation one, number n is selected, so we only need to select k-1 from n-1 next. Situation two, number n is not selected, and the rest job is selecting k from n-1.

    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            if (k == n || k == 0) {
                List<Integer> row = new LinkedList<>();
                for (int i = 1; i <= k; ++i) {
                    row.add(i);
                }
                return new LinkedList<>(Arrays.asList(row));
            }
            List<List<Integer>> result = this.combine(n - 1, k - 1);
            result.forEach(e -> e.add(n));
            result.addAll(this.combine(n - 1, k));
            return result;
        }
    }

  • 0
    S

    Could you explain what are you doing in your base condition within if?


  • 0
    K

    C(n,0) is an empty set, and C(n,n) is simply universal set {1,2,3,...,n}.


  • 2
    T

    This recursion will calculate duplicates, see C(3,2) on this image


  • 0
    T

    same idea, but iterative solution in Python:

    def combine(self, NN, K):
            result = [[[]]]
            for n in range(1, NN+1):
                lastRes = result[0]
                for k in range(1, min(K+1, n)):
                    #C(n, k) = C(n-1, k) + C(n-1, k-1)
                    lastRes, result[k] = result[k], result[k] + [_ + [n] for _ in lastRes]
                if n < K+1:
                    #C(n, n) = C(n-1, n-1) = 1
                    result.append([lastRes[0] + [n]]) 
            return result[K]
    

    My post.


  • 0
    S

    No, the two C(3,2) are not the same. The left C(3,2) does contain the number ' 5', while the right C(3,2) does not.


  • 0
    T

    C(3,2) cannot contain 5 because there are only 3 items to choose from. C(3,2) will always be (ignoring order): [[2, 3], [1, 3], [1, 2]]. Two recursive paths (5,3->4,2->3,2 and 5,3->4,3->3,2) will reach a combine(3,2) call, but it's higher on the stack that 5 will be added or not.


  • 0
    S

    Correction: The left C(3,2) belongs to a combination that contain the number ' 5', while the right C(3,2) does not. So the combinations are not the same.
    But yes, regarding the sub-combination itself, there are some duplicates in the recursion.


  • 2
    N

    I wrote your logic in C++

     vector<vector<int>> combine(int n, int k) {
            vector<vector<int> > res,res1;
           
            if(k==n || k==0)
            {
                vector<vector<int> > res2;
                vector<int> curr;
                for(int i=1;i<=k;i++)
                    curr.push_back(i);
                res2.push_back(curr);
                return res2;
            }
            
            res = combine(n-1,k-1);
            
            for(auto itr=res.begin();itr!=res.end();itr++)
            {
                itr->push_back(n);
            }
            
            res1 = combine(n-1,k);
            
            res.insert(res.end(),res1.begin(),res1.end());
            return res;
        }

  • 0
    X

    use dp to avoid computing duplicate


  • 1
    I
    public List<List<Integer>> combine(int n, int k) {
        if (k > n || k == 0) return new LinkedList<>();
        List<List<Integer>> ans = combine(n - 1, k - 1);
        if (ans.size() == 0) ans.add(new LinkedList<>(Arrays.asList(n)));
        else ans.forEach(e-> e.add(n));
        ans.addAll(combine(n - 1, k)); 
        return ans;
    }
    

  • 0

    Thanks for your sharing, and this is my c++ code with your method.

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            if (k == 0 || n == k) {
                vector<int> combination(k);
                for (int i = 1; i <= k; ++i)
                    combination[i - 1] = i;
                return vector<vector<int>>{ combination };
            }
            vector<vector<int>> combinations= combine(n - 1, k - 1);
            for (auto &combination : combinations)
                combination.push_back(n);
            auto subCombinations = combine(n - 1, k);
            combinations.insert(combinations.end(), subCombinations.begin(), subCombinations.end());
        	return combinations;
        }
    };
    

  • 1

    Although no very efficient, but this idea is pretty impressive. Thanks.


  • 0
    L

    I am confused about why use Arrays.asList


  • 0
    T

    @leaptwo notice the signature:
    List<List<Integer>>, so return must return a list of lists, the full explicit typed call would look like:
    return new LinkedList<List<Integer>>(Arrays.<List<Integer>>asList((List<Integer>)row));
    so asList is needed to create a list with a single list in it.

    Actually the new LinkedList<>() around it is redundant, because it's already the correct type after returning from asList; however it is needed because the calling code mutates the result which is not allowed by asList.


Log in to reply
 

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