script.m

    % Define funciton to prepend a cell x with a variable i
    cellprepend = @(x,i) {[i x]};

    % Execute and time function
    tic;
    a = allcomb(cellprepend,8);   % Solution in a
    toc;

allcomb.m

    function a = allcomb( cellprepend, n )
        % Add entire block as a combination
        a{1} = n;

        % Exit recursion if block size 1
        if n == 1
            return;
        end

        % Recurse cutting blocks at different segments
        for i = 1:n-1
            b = allcomb(cellprepend,n-i);
            a = [a cellfun( cellprepend, b, num2cell( stretchmat( i, b ) ) )];
        end
    end