Permutations 15

Question

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

递归求解，[]->[1]->[1,2]->[1,2,3]->[1,3]->[1,3,2]->[2]->[2,1]->[2,1,3]->[2,3]->[2,3,1]->[3]->[3,1]->[3,1,2]->[3,2]->[3,2,1]。原理为DFS。

非递归求解。

代码如下：

Recursion:

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
     //recursion vision
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        if(nums==null || nums.size()==0){
            return result;
        }

        ArrayList<Integer> list=new ArrayList<Integer>();
        helper(result,list,nums);
        return result;
    }

    public void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, ArrayList<Integer> nums){
        //将当前答案list加入result时不能将原有list加入，要新建一个并copy list的值后加入
        if(list.size()==nums.size()){
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i=0; i<nums.size(); i++){
            //若包含当前值则continue，直到找到不包含的加入list
            if(list.contains(nums.get(i))){
                continue;
            }
            list.add(nums.get(i));
            helper(result, list, nums);
            list.remove(list.size()-1);
        }
    }
}

Non-Recursion:

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
     //recursion vision
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        if(nums==null || nums.size()==0){
            return result;
        }

        int n=nums.size();

        //记录index
        ArrayList<Integer> pos=new ArrayList<Integer>();
        pos.add(-1);

        while(!pos.isEmpty()){
            int last=pos.get(pos.size()-1);
            pos.remove(pos.size()-1);

            int next=-1;

            //看删去的元素之后是否还有可以加入的元素
            for(int i=last+1; i<n; i++){
                if(!pos.contains(i)){
                    next=i;
                    break;
                }
            }//for

            //若没有可以加入元素，则继续删去上一位
            if(next==-1){
                continue;
            }

            //若有可以加入元素，则加入该元素，并加入其它为加入过的元素
            pos.add(next);
            for(int i=0; i<n; i++){
                if(!pos.contains(i)){
                    pos.add(i);
                }
            }//for

            ArrayList<Integer> list=new ArrayList<Integer>();
            for(int i=0; i<n; i++){
                list.add(nums.get(pos.get(i)));
            }
            result.add(list);
        }//while

        return result;
    }
}