# 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;
```