LeetCode - Permutations

Permutations.java

// Solution 1 : recursive

public ArrayList<ArrayList<Integer>> permute(int[] num) {
        if(num==null || num.length==0) return null;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        helper(num, new boolean[num.length], new ArrayList<Integer>(), ret);
        return ret;
    }
    
    private void helper(int[] num, boolean[] used, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> ret){
        if(temp.size()==num.length){
            ret.add(new ArrayList<Integer>(temp));
        }
        for(int i=0; i<num.length; i++){
            if(!used[i]){
                used[i] = true;
                temp.add(num[i]);
                helper(num, used, temp, ret);
                temp.remove(temp.size()-1);
                used[i] = false;
            }
        }
    }
    
// Solution 2: iterative
public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(num == null || num.length == 0) return ret;
        ret.add(new ArrayList<Integer>());
        for(int i=0; i<num.length; i++){
            ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
            for(int j=0; j<ret.size(); j++){
                for(int k=0; k<=ret.get(j).size(); k++){
                    ArrayList<Integer> lst = new ArrayList<>(ret.get(j));
                    lst.add(k, num[i]);
                    temp.add(lst);
                }
            }
            ret = temp;
        }
        return ret;
    }