Problem

Given a list of numbers, return all possible permutations.

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.

Solution

Recursion

class Solution {
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.size() == 0) {
            return res;
        }
        ArrayList<Integer> list = new ArrayList<Integer> ();
        helper (nuts, list, res);
        return res;
    }
    
    public void helper(ArrayList<Integer> num, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> res) {
        if (list.size() == num.size()) {
            res.add(new ArrayList<Integer> (list));
            return;
        }
        for (int i = 0; i < num.size(); i++) {
            if (list.contains(num.get(i))) {
                continue;
            }
            list.add(num.get(i));
            helper(num, list, res);
            list.remove(list.size() - 1);
        }
    }
}

Iteration

class Solution {
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.size() == 0) return res;
        res.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.size(); i++) {
            ArrayList<ArrayList<Integer>> cur = new ArrayList<ArrayList<Integer>>();
            for (ArrayList<Integer> list: res) {
                for (int index = 0; index <= list.size()-1; index++) {
                    ArrayList<Integer> curlist = new ArrayList<Integer>(list);
                    curlist.add(index, nums.get(i));
                    cur.add(curlist);
                }
                ArrayList<Integer> curlist = new ArrayList<Integer>(list);
                curlist.add(nums.get(i));
                cur.add(curlist);
            }
            res = cur;
        }
        return res;
    }
}

Olivia's Iteration: (I love this!)

class Solution {
    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;
        //put first element in res
        res.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.size(); i++) {
            //all about nums[]<--list<--res==cur-->curlist-->nums[] in the loop
            ArrayList<ArrayList<Integer>> cur = new ArrayList<ArrayList<Integer>>();
            for (ArrayList<Integer> list: res) {
                //How smart(薅聪命)
                for (int index = 0; index < list.size()+1; index++) {
                    ArrayList<Integer> curlist = new ArrayList<Integer> (list);
                    curlist.add(index, nums.get(i));
                    cur.add(curlist);
                }
            }
            res = cur;
        }
        return res;
    }
}