Permutations

medium

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]
]

Analysis

经典Backtracking问题，除了常规模板的add - backtrack - remove循环，LeetCode官方给的解法中是用了一个swap的方法。

Solution

Backtracking - Add Remove (6ms 34.59%）

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        boolean[] visited = new boolean[nums.length];

        // Totla number of permutations: n! = n * (n - 1) * ... 3 * 2 * 1
        permuteHelper(nums, visited, new LinkedList<>(), ans);
        return ans;
    }

    private void permuteHelper(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> ans) {
        // When a permutation reaches the desired length, add a COPY to ans
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            list.add(nums[i]);
            visited[i] = true;
            permuteHelper(nums, visited, list, ans);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

这个方法很直观，但是复杂度怎么分析呢？每进入一个permuteHelper()就需要进行O(n)循环，但是进入下一层permuteHelper会减少一个，因为本层中使用了一个nums[i]，会在下一层中跳过上一层用过的数字，而这个树状结构有多少层呢？因为只有在list.size() == nums.length的时候才会返回，因此总共有n层，而各层汇总之后： n * (n - 1) * (n - 2) * ... * 2 * 1

也就是O(n!)的时间复杂度。当然也可以用全排列的本身数学性质得到这一点。

Backtracking - Swap - LeetCode Official (4ms 90.37%)

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();

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

Time complexity : O(N!) to build N! solutions.

Space complexity : O(N!) since one has to keep N! solutions.