Leetcode: Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Solution: Extra space O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>> ();
        HashSet<Integer> used = new HashSet<Integer>();
        ArrayList<Integer> oneSolution = new ArrayList<Integer>();
        permute(num, used, solution, oneSolution);
        return solution;
    }
    private void permute(int[] num, HashSet<Integer> used, ArrayList<ArrayList<Integer>> solution, ArrayList<Integer> oneSolution) 
    {
        if(oneSolution.size()==num.length)
        {
            solution.add(oneSolution);
            return;
        }
        for(int i=0; i< num.length; i++)
        {
            if(!used.contains(num[i]))
            {
                used.add(num[i]);
                ArrayList<Integer> tempSolution = (ArrayList<Integer>) oneSolution.clone();
                tempSolution.add(num[i]);
                permute(num, used, solution, tempSolution);
                used.remove(num[i]);
            }
        }
    }
}

Solution 2: Swap based (No additional data structures)

public class Solution {

    public ArrayList<ArrayList<Integer>> permute(int[] num) {

        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>> ();

        permute(num, 0, solution);

        return solution;

    }

   

    private void permute(int[] num, int index, ArrayList<ArrayList<Integer>> solution) 

    {

        if(index+1==num.length)

        {

            ArrayList<Integer> sol= new ArrayList<Integer>();

            for (int i=0; i<num.length; i++)

                sol.add(num[i]);

            solution.add(sol);

            return;

        }

        permute(num, index+1, solution);

        for(int i=index+1; i<num.length; i++)

        {

            swap(num, index,i);

            permute(num, index+1, solution);

            swap(num, i, index);

        }

    }

    

    private void swap(int[] num, int i, int j)

    {

        int temp = num[i];

        num[i] = num[j];

        num[j] = temp;

    }

}