How can I solve the zero subset sum problem with hill climbing?
The hill-climbing algorithm to implement is as follows:


The algorithm should take four inputs: as always, there will be a multiset S and integer
k, which are the Subset and Sum for the Subset Sum problem; in addition, there
will be two integers q and r, with roles defined below.
Do the following q times:


(a) Choose a random subset (multiset) $S_0$ of S as the current subset.

(b) Do the following (hill climbing) r times:

i. Find a random neighbor T (see definition of neighbor below) of the current
subset.

ii. If neighbor T has smaller residue, then make T the current subset.

(c) Keep track of the residue of the final current subset when starting with subset
$S_0$.


Return the smallest residue of the q subsets tested by the algorithm.


Definition: Subset (multiset) B ⊆ S is a neighbor of a subset A of S if you can transform
A into B by moving one or two integers from A to B, or by moving one or two integers from
B to A, or by swapping one integer in A with one integer in B.
An easy way to generate a random neighbor B of a subset A of S is as follows:


Order the elements of S as $x_1, x_2, ..., x_n$.
Initialize B to be a clone of A.
Choose two distinct random indices i and j, where $1 ≤ i; j ≤ n$.
if $x_i$ is in A, remove it from B. Otherwise, add xi to B.
if $x_j$ is in A, then with probability 0.5, remove it from B. If $x_j$ is not in A, then with
probability 0.5, add $x_j$ to B.