leetcode题解(46) Permutations(全排列)

题目描述：Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]

Output:

[

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

]

解题思路：与剑指offer第27题相似，求一个数组的全排列。借用一张图来展述思路：

运用递归思想，依次交换当下索引数值与剩余数组数值，然后改变当下索引下标，判断下标值，如果达到边界则把当下数组顺序加入到集合中。依次递归。

代码如下：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> newList = new ArrayList<>();
        permute(0, nums, newList);
        return newList;
        
    }
    
    public void permute(int k, int[] nums, List<List<Integer>>newList) {
        if (k == nums.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++)
                list.add(nums[i]);
            newList.add(list);
            return;
        }
        
        for (int i = k; i < nums.length; i++) {
            swap(nums, i, k);
            permute(k + 1, nums, newList);
            swap(nums, k, i);
                
            }
            
    }   
        
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        
    }
    
}