Codeforces problem Java code optimization

Question

The problem says:

You are given an array a of length 2n. Consider a partition of array a into two subsequences p and q of length n each (each element of array a should be in exactly one subsequence: either in p or in q).
Let's sort p in non-decreasing order, and q in non-increasing order, we can denote the sorted versions by x and y, respectively. Then the cost of a partition is defined as f(p,q)=∑i=1ⁿ|xi−yi|.
Find the sum of f(p,q) over all correct partitions of array a. Since the answer might be too big, print its remainder modulo 998244353.

Input:
The first line contains a single integer n (1≤n≤150000). The second line contains 2n integers a1,a2,…,a2n (1≤ai≤10^9) — elements of array a.

Output:
Print one integer — the answer to the problem, modulo 998244353.

My solution generates all combinations of size n from a, then goes through each pair of combinations that complement each other, sorts them, and finally calculates the cost. Here is the code:

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

     public static void main(String []args)
     {
        Scanner in = new Scanner(System.in);
        
        // reads the values 
        int k = in.nextInt();
        int[] input = new int[2 * k];
        for (int i = 0; i < 2 * k; i++) {
            input[i] = in.nextInt();
        }
    
        List<int[]> combinations = new ArrayList();
        int[] indices = new int[k];
        
        //generates all valid combinations of size k, choosing k 
        for(int i = 0; (indices[i] = i) < k - 1; i++);
        combinations.add(getCombination(input, indices));
        for (;;) {
            int i;
            for (i = k - 1; i >= 0 && indices[i] == input.length - k + i; i--); 
            if (i < 0) {
            break;
            }
            indices[i]++;
            for (++i; i < k; i++) {    
                indices[i] = indices[i - 1] + 1; 
            }
            combinations.add(getCombination(input, indices));
        }
        //for depugging
        //combinations.forEach(e -> System.out.println(Arrays.toString(e)));
        //int[] temp1, temp2;
        
        //goes through all pairs that complement each other and calculates the cost for each
        int theSum = 0;
        for (int i = 0, j = combinations.size() - 1; i < combinations.size() && j >= 0; i++, j--) {
          //  temp1 = combinations.get(i);
          //  temp2 = combinations.get(j);
            Arrays.sort(combinations.get(i));
            Arrays.sort(combinations.get(j));
            reverse(combinations.get(j));
            //for debugging
            //System.out.println(Arrays.toString(temp1) + ", " + Arrays.toString(temp2));
            theSum += cost(combinations.get(i), combinations.get(j));
        }
        System.out.println(theSum % 998244353);
    }
    public static int[] getCombination(int[] input, int[] indices) {
         int[] result = new int[indices.length]; 
        for (int i = 0; i < indices.length; i++) 
            result[i] = input[indices[i]];
        return result;
    }
    public static int cost(int[] x, int[] y) {
        int sum = 0;
        for (int i = 0; i < x.length; i++) {
            sum += Math.abs(x[i] - y[i]);
        }
        return sum;
    }
    public static void reverse(int[] array) {
        for(int i = 0; i < array.length / 2; i++) { 
            int temp = array[i]; 
            array[i] = array[array.length - i - 1]; 
            array[array.length - i - 1] = temp; 
        }
    }
}

The memory usage exceeded 512 MB and I don't know if I should change the data structures, or the algorithms, or both. I would appreciate any suggestions.