Permutations

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].

public class Solution {

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

        // Start typing your Java solution below

        // DO NOT write main() function

        ArrayList<ArrayList<Integer>> permutations =

               new ArrayList<ArrayList<Integer>>();

        permutations.add(new ArrayList<Integer>());

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

            int currentSize = permutations.size();

            for (int j=0; j<currentSize; j++) {

                ArrayList<Integer> sub = permutations.get(0);

                permutations.remove(sub);

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

                    ArrayList<Integer> newSub = new ArrayList<Integer>(sub);

                    newSub.add(k,num[i]);

                    permutations.add(newSub);

                }

            }

        }

        return permutations;

    }

}