# Permutations

## Question ([LC.46](https://leetcode.com/problems/permutations/))

> Given a collection of numbers, return all possible permutations.

input contains duplicate number? NO.\
input sorted? doesn't matter\
input size? < 15

## Example

```
([1,2,3]) => [
    [1,2,3], [1,3,2],
    [2,1,3], [2,3,1],
    [3,1,2], [3,2,1]
]
```

3!

## Analysis

How is this different from subsets?

```
we can use the previous candidates that are not used at this level

          []
         [1]
        /   \
    [1,2]   [1, 3]
    /          \!!! we can still add 2 here (not in subsets)
[1,2,3]     [1, 3, 2]


Think of it we are doing a bfs at each level [1, ?]
```

## Approach

The way it exhausts the search space is slightly different than combinations. Since the order does not matter, we can reuse elements that are smaller than the current element.

```
1 Define recursion
generate all possible permutations with elements that are not inPerm
genPerms(List<List<Integer>> results, int[] nums, List<Integer> perm, boolean[] inPerm)

2 Recursive calls
for each element not inPerm
    perm.add(ele)
    inPerm[ele] = true
    genPerms(results, nums, perm, inPerm)

3 Base case
if (perm.size() == nums.length)
    results.add(new Perm)
    return
```

## Code

```java
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    // edge check
    if (nums == null) return results;
    // kick off helper
    List<Integer> perm = new ArrayList<>();
    boolean[] inPerm = new boolean[nums.length];
    genPerms(results, nums, perm, inPerm);
    return results;
}

private void genPerms(List<List<Integer>> results, 
                      int[] nums, 
                      List<Integer> perm, 
                      boolean[] inPerm) {
    // base case
    if (perm.size() == nums.length) {
        results.add(new ArrayList<>(perm));
        return;
    }
    // recursive calls
    for (int i = 0; i < nums.length; i++) {
        if (inPerm[i]) continue;
        perm.add(nums[i]);
        inPerm[i] = true;
        genPerms(results, nums, perm, inPerm);
        perm.remove(perm.size() - 1);
        inPerm[i] = false;
    }
}
```

## Time Complexity

`Time = #subproblems * time/subproblem = O(n!) * O(n) = O(n*n!)`

## To Do

insertion iterative approach

swapping approach??

## Follow Up Question ([LC.47](https://leetcode.com/problems/permutations-ii/))

What if the input has duplicates?

For example, given input `[1, 2, 2]`, we have $$\frac{3!}{2!1!}$$ permutations (with repetition). We are eliminating 3 cases where the second '2' is swapped with the first '2'. We want $$\[1, 2\_1, 2\_2]$$ instead of $$\[1, 2\_2, 2\_1]$$. Therefore, once the input is sorted, we need to skip the current element when it is the same as the previous element and the previous element is not used.

```java
if (i != 0 && nums[i-1] == nums[i] && !used[i-1]) continue;
```


---

# 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://zedive.gitbook.io/project-l/part-2/graph-search/exhaustive-search/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.