All permutations of the pairs that add to squares Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number.
  
  E.g: Given an input number of 16, one of the possible answers would be:

8:1:15:10:6:3:13:12:4:5:11:14:2:7:9:16

  
  and its reverse.


Note that the function called hasIntegerRoot has been commented out for a purpose. I would appreciate if reviewer would chose me to use hasIntegerRoot over currently used List&lt;Integer&gt; squareList.

I'm looking for code review, best practices, optimizations etc. 

Verifying Complexity (where \$n\$ is the input number):


Time: \$O(n!)\$
Space: \$O(n!)\$




public final class PairSquare {

    private PairSquare() {};

    /**
     *  Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number"
     * 
     * @param num        The number upto which adjacent numbers should sum to a sqaure 
     * @return           A List of all the lists/chains of integers such that adjacent numbers sum upto a square.
     */
    public static List&lt;List&lt;Integer&gt;&gt; pairSquare (int num) {
        if (num &lt;= 0) throw new IllegalArgumentException("The input number " + num + " should be less than equal to zero.");

        final List&lt;List&lt;Integer&gt;&gt; pairSquaresList = new ArrayList&lt;List&lt;Integer&gt;&gt;();
        final List&lt;Integer&gt; squareList = squareList(num);
        final LinkedHashSet&lt;Integer&gt; elements = new LinkedHashSet&lt;Integer&gt;();
        for (int i = 1; i &lt;= num; i++) { 
            elements.add(i);
            getSqaureLists(i, num, elements, pairSquaresList, squareList);
            elements.remove(i);
        }
        return pairSquaresList;
    }

    private static List&lt;Integer&gt; squareList(int num) {
        int limit = num + (num  - 1);
        int n = 2;
        final List&lt;Integer&gt; sqaureList = new ArrayList&lt;Integer&gt;();
        int square;
        while ((square = n * n) &lt;= limit) {
            sqaureList.add(square);
            n++;
        }
        return sqaureList;
    }

//    private static boolean hasIntegerRoot(int x) {
//        double root = Math.sqrt(x);
//        return  root == (int)root;
//    }

    private static void getSqaureLists(int currNum, int num, LinkedHashSet&lt;Integer&gt; elements, List&lt;List&lt;Integer&gt;&gt; pairSquareList, List&lt;Integer&gt; squareList) {
        if (elements.size() == num) {
            pairSquareList.add(new ArrayList&lt;Integer&gt;(elements));
            return;
        }

        for (int i = 1; i &lt;= num; i++) {
            // a number has already been added in the list. deduping.
            if (elements.contains(i))  continue;

//            // checking if the adjacent numbers add up to a square of an int.
//            if (hasIntegerRoot(i + currNum)) {
//                elements.add(i);
//                getSqaureLists(i, num, elements, pairSquareList, squareList);
//            }

            if (squareList.contains(i + currNum)) {
                elements.add(i);
                getSqaureLists(i, num, elements, pairSquareList, squareList);
            }

            elements.remove(i);
        }
        return;
    }

    public static void main(String[] args) {
        List&lt;Integer&gt; list1 = Arrays.asList(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16);
        List&lt;Integer&gt; list2 = Arrays.asList(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8);

        List&lt;List&lt;Integer&gt;&gt; listOfLists = new ArrayList&lt;List&lt;Integer&gt;&gt;();
        listOfLists.add(list1);
        listOfLists.add(list2);

        Assert.assertEquals(listOfLists, pairSquare(16));
    }
}
Since you don't seem to be concerned with the order of any of the collections of objects you use, only membership in those collections, Set is probably the better Collection to use, instead of List.  I imagine that Set.contains is going to be more efficient than List.contains.

Also, it's not clear to me that recursion is the way to go here.  If I were you, I would try to walk through the code with a low value for the input number and see what it's doing.  It looks like for every integer between 1 and num, you're calling getSqaureLists num x num times.  That seems like overkill.  Recursion typically does some work and then passes a smaller set of work to the recursive call.  You need to clarify how you split up that work.  If that's not working, a iterative solution might be clearer.  

You also have some code to check for duplicates.  You shouldn't need to do that.  Whether you a doing an iterative or recursive solution, you should be able to avoid ever testing duplicate values.