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;
        
    }
    
}