全排列 -- LeetCode[46]

【Medium】给定一个没有重复数字的序列，返回其所有可能的全排列。

举例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

回溯法
关于回溯法的其他题型，看这里

回溯法的算法原型是：
通过探索所有可能的候选解来找出所有的解。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

其实回溯算法关键在于:
不合适就退回上一步
然后通过约束条件, 减少时间复杂度。

题解一

public class Solution46 {
  public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> res = new ArrayList<>();
    int[] visited = new int[nums.length];//用来标识，当前递归链中，某个索引下的值是否被使用过了。
    backtrack(res, nums, new ArrayList<Integer>(), visited);
    return res;

  }

  private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
    if (tmp.size() == nums.length) {
      res.add(new ArrayList<>(tmp));
      return;
    }
    for (int i = 0; i < nums.length; i++) {
      if (visited[i] == 1)//如果这个值被使用过了，那么就继续用下一个
        continue;
      tmp.add(nums[i]);//加入链表
      visited[i] = 1;//标记这个值被使用过了

      backtrack(res, nums, tmp, visited);
      //回溯
      visited[i] = 0;
      tmp.remove(tmp.size() - 1);
    }
  }
}

这个解法是我看到的第二个解法（因为第一个解法，也就是下面的解法，第一次没看懂[哭]）。这个解法其实一眼就看出来了。

和概率论中的摸球题思想有点类似。

N个Value，先固定第一个，N个值里去找第二个。
怎么去找N个Value里的那个第二个值，而不和第一个重复呢？题解里，用一个visited来标识这个值是否已经被用过。
找到一个解之后，就通过回溯的方式，再去寻找下一个解。

这就是回溯的基本思想。

看完上一个题解之后，其实发现，在N个value中找第二个值的方式似乎可以优化。
于是有了下面这个题解。

题解二

class Solution {
    public void backtrack(int n, ArrayList<Integer> nums, List<List<Integer>> output, int first) {
        // if all integers are used up
        if (first == n)
            output.add(new ArrayList<Integer>(nums));

        for (int i = first; i < n; i++) {
            // place i-th integer first
            // in the current permutation
            Collections.swap(nums, first, i);
            // use next integers to complete the permutations
            backtrack(n, nums, output, first + 1);
            // backtrack
            Collections.swap(nums, first, i);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        // init output list
        List<List<Integer>> output = new LinkedList<List<Integer>>();

        // convert nums into list since the output is a list of lists
        ArrayList<Integer> nums_lst = new ArrayList<Integer>();
        for (int num : nums)
            nums_lst.add(num);

        int n = nums.length;
        backtrack(n, nums_lst, output, 0);
        return output;
    }
}

这是这道题 LeetCode的官方题解。

题解一中的tmp链表，其实是用来探索并且存储一个解。但是这个解其实可以直接存储在原始链表内，通过swap，交换元素位置，来得到一个解。而回溯的时候，只需逆向的swap即可。

举个例子，加入有N个value，记作 Arr[N]，算法流程：

固定第一个value，一共有N种可能性。所以遍历索引i<N，并且把Arr[i]与第一个交换。那么剩下来的事情，就变成：把剩余N-1个值排列出所有的可能性。
不断的递归第1步，只不过每次固定的是剩余的Value中的第一个值，一直到最后一个值。这个时候，Arr中的就是其中的一个解了。
接下来就是回溯，回溯的方法就是反向swap。每次循环都是一个回溯。

算法复杂度：

第一个递归是N次循环，第二个递归是N-1次，第三个是N-2次…
时间复杂度应该是：O(n!)题解一的时间复杂度为O(n^n)
空间复杂度应该是：O(1) 题解一的空间复杂度是O(n)

与此题型类似的有: