算法14 Permutations

题目:给出不同的数字的集合，返回所有可能的排列组合。
例如，
[1,2,3] 有如下的排列组合：

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

思路：根据题意输入数据中无重复元素。以递归方式找出所有排列。每次循环给出的数组时，判断temp中是否有该元素，当全部都在temp中时，加入list中。

代码：
public static void main(String[] args) throws Exception {
int[] num = {1,2,3};
permute(num);
}

public static List<List<Integer>> permute(int num[]){
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    backtrack(list,new ArrayList<Integer>(), num);
    return list;
}

public static void backtrack(List<List<Integer>> list,List<Integer> temp,int[] num){
    if(temp.size()==num.length){
        list.add(new ArrayList<Integer>(temp));
    }else {
        for (int i = 0; i < num.length; i++) {
            //若临时list中有这个值，则结束本次循环继续下个循环
            if(temp.contains(num[i])) continue;
            temp.add(num[i]);
            backtrack(list,temp,num);
            //list中加入一个新temp时和循环结束时，temp去掉最后一个元素
            temp.remove(temp.size()-1);
        }
    }
}