Changing URL from /%postname%/%post_id to /%category%/%postname%/%post_id%

So first, I’m quoting @MrWhite’s comment:

You can’t do that sort of redirect in .htaccess – where are you
expected to get the posts-category part from?

And he’s right — you shouldn’t use the .htaccess.

We have over 2,000 articles and 55,000 backlinks to these articles. If
I just change the permalinks I will have over 50k 404s which will
break the site.

You should just change the permalink structure and use custom code to redirect old URLs to the new ones.

Step 1: Change the permalink structure.

Just go to the Permalink Settings page and in the Custom Structure box, enter this:

/%category%/%postname%/%post_id%/

Step 2: Add custom PHP/WordPress code to redirect old URLs to new ones.

This is an example (tried and tested working) using the parse_request hook: (this would go in your theme functions.php file) (and the code uses these two WordPress functions: get_post_field() and wp_redirect())

add_action( 'parse_request', 'maybe_redirect_old_permalinks' );
function maybe_redirect_old_permalinks( $wp ) {
    if ( preg_match( '#^([^/]+)/(\d+)$#', $wp->request, $matches ) ) {
        list ( $path, $slug, $id ) = $matches;
        // Redirect to the new permalink, if the slug and ID match.
        if ( $slug === get_post_field( 'post_name', $id ) ) {
            wp_redirect( get_permalink( $id ), 301 );
            exit;
        }
    }
}

This approach also means that both example.com/<post slug>/<post ID> and example.com/<post category>/<post slug>/<post ID> would work. But on the page (post content, widgets, etc.), post permalinks would only be in the later format.