Permutations

Question (LC.46)

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

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)

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.

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