学步园

题目：

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],
and [3,2,1].

思路：

递归解决。第一层：将每一个元素跟该递归层第一个元素进行交换，放入list，然后进入下一层。当下一层返回之后，删除list刚加入的那个元素（list的末尾元素），然后将原来那个元素交换回来，并将后面一个元素跟该层第一个原始元素交换。再进入下一层。直到将最后一个元素跟第一个元素交换完成为止。则针对当前层的上一层的某个元素而言，它后面的所有排列都已经完成列举。最里层发生的情况：该层对应的元素是数组的最后一个元素（或者该层对应的元素下标超出数组最后一个下标，其实没什么太大区别，仅仅是多递归了一层），则将该元素放入list并将list复制放入最终数组rst。

AC代码:

public class Permutations {
    private LinkedList<Integer> tmp = new LinkedList<Integer>();
    private List<List<Integer>> rst = new LinkedList<List<Integer>>();

    private void perMu(int start, int[] num) {
        if (start == num.length) {
            List<Integer> tmpp = new LinkedList<Integer>();
            for (Integer tm : tmp) {
                tmpp.add(tm);
            }
            rst.add(tmpp);
        } else {
            for (int i = start; i < num.length; i++) {
                int t = num[start];
                num[start] = num[i];
                num[i] = t;
                tmp.add(num[start]);
                perMu(start + 1, num);
                tmp.removeLast();
                t = num[i];
                num[i] = num[start];
                num[start] = t;
            }
        }
    }

    public List<List<Integer>> permute(int[] num) {
        if (num == null || num.length == 0)
            return rst;
        perMu(0, num);
        return rst;
    }

    public static void main(String[] args) {
        Permutations permutations = new Permutations();
        int[] num = {1, 2};
        System.out.println(permutations.permute(num));
    }
}