Permutations

Given a list of numbers, return all possible permutations.

Have you met this question in a real interview? 

Yes

Example

For nums = [1,2,3], the permutations are:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Challenge

Do it without recursion.

class Solution {

    /**

     * @param nums: A list of integers.

     * @return: A list of permutations.

     */

    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {

        // write your code here

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

        if(nums == null || nums.size() == 0) return res;

        permuting(nums, new HashSet<Integer>(), new ArrayList<Integer>(), res);

        return res;

    }

    

    private void permuting(ArrayList<Integer> nums, HashSet<Integer> visited, ArrayList<Integer> subList,  ArrayList<ArrayList<Integer>> res){

        if(subList.size() == nums.size()){

            res.add(new ArrayList<Integer>(subList));

            return;

        }

        

        for(int i = 0; i < nums.size(); i++){

            if(!visited.contains(nums.get(i))){

                subList.add(nums.get(i));

                visited.add(nums.get(i));

                permuting(nums, visited, subList, res);

                visited.remove(nums.get(i));

                subList.remove(subList.size()-1);

            }

        }

    }

}

iterative

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(nums == null) return res;
        res.add(new ArrayList<Integer>());
        
        for(int i = 0; i < nums.size(); i++){
            int num = nums.get(i);
            ArrayList<ArrayList<Integer>> temp = res;
            res = new ArrayList<ArrayList<Integer>>();
            for(ArrayList<Integer> list : temp){
                for(int j = 0; j < list.size() + 1; j++){
                    list.add(j, num);
                    res.add(new ArrayList<Integer>(list));
                    list.remove(j);
                }
            }
        }
        return res;
    }
}