It seems that the original problem can be convert to the further-thought problem by plussing 1 to the set S2, and
get solved quickly.

I don’t think your code works. For number 10, there are two ways to get it, 7+3 and 6+4, but for number 9, there are three ways to get it, 7+2, 6+3, and 5+4. In a word, their probabilities are not equals.

void double_square(int x){
// Searhc in a matrix of i rows and j cols. Value of element(i, j) is (i*i + j*j). O(sqrt(x))
int i, j, n, s;
n = (int)sqrt(x);
for(i = n, j = 0; i >= j;){
s = […]

It’s better to consider the overlap problem of two lines firstly, because this one is easier to solve and gives good hits to our real problem.