Problem3.java

import java.util.*;

public class Problem3 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int testCases = scan.nextInt();
        List<Integer> numbers = new ArrayList<>();

        for ( int i =1; i<=testCases; ++i) {
            numbers.add(scan.nextInt());
        }

        for (Integer number : numbers) {
            findPairs(number);
        }



    }

    private static void findPairs(Integer number) {

        HashSet<Pair> pairs = new HashSet<>();


        for(int i=10;i <=number; ++i) {

            int a = i;
            //System.out.println("Trying " + a);
            ArrayList<Integer> digitsArray =getDigitsArray(a);
            for(int j =0; j< digitsArray.size(); ++j) {
                List<List<Integer>> permutations = listPermutations(digitsArray);

                for(List<Integer> list: permutations) {

                    for (int k =0; k<list.size(); ++k) {

                        ArrayList<Integer> copyArray = new ArrayList<Integer>(list);
                        copyArray.remove(k);
                        int b = convertToNumber(copyArray);

                        if(a + b == number && a != b) {
                          //  System.out.println("Found pair for: " + a);
                            pairs.add(new Pair(a,b));
                        }

                    }
                }

            }

        }

        System.out.println(pairs.size() + " pairs found");

        for(Pair pair: pairs) {
            System.out.println(pair);
        }

    }



    private static Integer convertToNumber(ArrayList<Integer> digits) {
        Integer number = 0;

        for (int digit : digits) {
            number *= 10;
            number += digit;
        }

        //System.out.println("Array is " + digits + "Number is: " + number);
        return number;
    }

    public static List<List<Integer>> listPermutations(List<Integer> list) {

        if (list.size() == 0) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            result.add(new ArrayList<Integer>());
            return result;
        }

        List<List<Integer>> returnMe = new ArrayList<List<Integer>>();

        Integer firstElement = list.remove(0);

        List<List<Integer>> recursiveReturn = listPermutations(list);
        for (List<Integer> li : recursiveReturn) {

            for (int index = 0; index <= li.size(); index++) {
                List<Integer> temp = new ArrayList<Integer>(li);
                temp.add(index, firstElement);
                returnMe.add(temp);
            }

        }
        return returnMe;
    }


    private static ArrayList<Integer> getDigitsArray(int number) {

        int temp = number;
        ArrayList<Integer> array = new ArrayList<Integer>();
        do{
            array.add(temp % 10);
            temp /= 10;
        } while  (temp > 0);

        return array;
    }

}