# 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%）

```java
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%)

```java
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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/backtracking/permutations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.