Prove that this solution to the Closest 3-Sum problem always works I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.
Here's the problem, transcribed:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

The top solution was basically this:

Sort the list.
Loop over each number using index i.
Pick j to be i+1, in other words, the leftmost number of the segment after i.
Pick k to be n-1, in other words, the rightmost number of the segment after i.
If the sum of the numbers at (i, j, k) are less than the target, then j++. Otherwise, k--.

But isn't it possible that we might prematurely increment j (or decrement k), dismissing it forever, when in fact it may have been the optimal pairing had we tried a different k (or j)?
It seems we'll never backtrack to check other combinations.
Can someone provide a minimal, intuitive proof of why such a case never occurs? I'm unable to come up with a counterexample, and I trust the experienced members of Leetcode, so I know I must be wrong, but I can't seem to prove it. I can prove it for the Exact 3-Sum problem, but I don't know how to work with inequalities.
The core of the problem is to solve the 2 sum closest problem for a particular i:

Given a target value, find a pair of numbers who's sum is closer to the target value.

The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right)

Your question is why can we decrease r or increase l. 

The answer is as the array is sorted, and suppose nums[r] + nums[l] &lt; target, we would not gain any better result comparing nums[l] with any of the values of nums between l and r. Because for any other value in nums[l to r] the sum is even smaller.
 As we wouldn't get any better result, why not forget about the value nums[l] all together? Right?
And that is what we do by increasing l.

This reasoning happens since the beginning of the 2 sum closest search. When l=0 and r=len(nums). We discard values one by one until we are left with l=r-1.