(UVA) Sum It Up - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=515

The solution below is using backtracking. All the possible sums among the given numbers are tested in order to achieve the required sum.


import java.io.*;
import java.util.*;

class Main {
    public static int qtyNumbers;
    public static int[] numbers;
    public static int finalSum;
    public static ArrayList<Integer> seq;
    public static HashSet<ArrayList<Integer>> control;
    public static ArrayList<ArrayList<Integer>> finalSeq;
   
    public static void rec(int index, int sum) {
        if (sum > finalSum) {
            return;
        }
        if (sum == finalSum) {
            if (!control.contains(seq)) {
                control.add((ArrayList<Integer>) seq.clone());
                finalSeq.add((ArrayList<Integer>) seq.clone());
            }
           
            return;
        }
       
        for (int i = index+1; i < qtyNumbers; i++) {
            seq.add(numbers[i]);
            rec(i, sum+numbers[i]);
            seq.remove(seq.size()-1);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        finalSum = sc.nextInt();
        qtyNumbers = sc.nextInt();
        while (finalSum != 0 || qtyNumbers != 0) {
            numbers = new int[qtyNumbers];
            for (int i = 0; i < qtyNumbers; i++) {
                numbers[i] = sc.nextInt();   
            }
           
            seq = new ArrayList<>();
            control = new HashSet<ArrayList<Integer>>();
            finalSeq = new ArrayList<ArrayList<Integer>>();
           
            System.out.println("Sums of " + finalSum + ":");
            rec(-1, 0);
            if (finalSeq.size() == 0) {
                System.out.println("NONE");
            }
            else {
                for (int i = 0; i < finalSeq.size(); i++) { // 4
                    for (int j = 0; j < finalSeq.get(i).size()-1; j++) { // 1
                        System.out.print(finalSeq.get(i).get(j) + "+");
                    }
                    System.out.println(finalSeq.get(i).get(finalSeq.get(i).size()-1));
                }
            }
                   
            finalSum = sc.nextInt();
            qtyNumbers = sc.nextInt();
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}