46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>(); 
        tempPermute(nums, 0, res);
        return res;
    }
    
    public void tempPermute(int[] nums, int start, List<List<Integer>> res) {       
        if(nums.length - start < 2) {   //递归结束
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i : nums) {
                tmp.add(i);
            }
            res.add(tmp);
            return;
        }
        // 把后面的数组元素交换到start位置,并对start+1剩下的元素进行全排列    
        for(int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            tempPermute(nums, start + 1, res);
            swap(nums, start, i); // 部分全排完成再交换回去!!!
        }
    }
    
     private static void swap(int[] nums, int i1, int i2) {
        int temp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = temp;
    }
}