Combination Sum

/*
 * Problem : Ways to reach the target.
 * Input   : n, the numbers, then k.
 * Output  : One way per line.
 * Approach: Backtracking.
 * Time    : O(number of ways * length)
 * Space   : O(target)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Try the numbers from index "start" on. Going back to a smaller index is not allowed, so no way repeats.
        static void search(int[] numbers, int start, int remaining, java.util.ArrayList<Integer> current, java.util.List<String> found) {
            // Step 2: Base case. When nothing remains, the current choice is a way.
            if (remaining == 0) {
                StringBuilder line = new StringBuilder();
                for (int i = 0; i < current.size(); i++) {
                    line.append(i == 0 ? "" : " ").append(current.get(i));
                }
                found.add(line.toString());
                return;
            }
            for (int i = start; i < numbers.length && numbers[i] <= remaining; i++) {
                // Step 3: Choose the number, search again from the same index (reuse is allowed), then remove it (backtrack).
                current.add(numbers[i]);
                search(numbers, i, remaining - numbers[i], current, found);
                current.remove(current.size() - 1);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a, int k) {
        // Step 4: Sorting lets us stop early and gives the lines in lexicographic order.
        int[] numbers = a.clone();
        java.util.Arrays.sort(numbers);
        java.util.List<String> found = new java.util.ArrayList<>();
        search(numbers, 0, k, new java.util.ArrayList<>(), found);
        if (found.isEmpty()) {
            return new String[] {"none"};
        }
        return found.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(String.join("\n", solve(a, k)));
    }
}