LeetCode 46. Permutations

Problem

LeetCode 46. Permutations

1. 题目简述

给出一列不重复整数，找出其所有的全排列。例如：

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

2. 算法思路

back tracking回溯法的经典题目之一，要注意和subset以及combination sum不同的是，这里是要找排列，而不是子集合，思路有很大的不同。

首先我们先来找一下规律，对于上面的例子，不外乎就是找到以1开头的所有排列，和以2开头的所有排列以及以3开头的所有排列。

我们对于以1开头的全排列，就是“1 + 2和3的全排列”，然后我们再以同样的思路去找2和3组成的全排列，2和3的全排列就是以2开头，找3的全排列和以3开头找2的全排列。2和3都是单独的数字时，其全排列只有一种，返回。

那么我们如何去将各种不同的开头的可能性都给找出来呢？我们只需要将某数字和后面的数字轮流置换即可，找完一个以后再换回来，然后和下一个进行置换，直到首个字母和最后一个字母进行置换完成。

回溯法

回溯法置换当前数字和其后面的数字，然后递归调用。

时间复杂度：O(2 ^ n)，空间复杂度：O(n)。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> res = new ArrayList();

        if (nums.length == 0) {
            return res;
        }

       getPermutations(nums, 0, res);

       return res;
    }

    private void getPermutations(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length - 1) {
            List<Integer> solution = new ArrayList();
            for (int num : nums) {
                solution.add(num);
            }
            res.add(solution);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            getPermutations(nums, i + 1, res);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}