Permutations

Getting all ordered sequence by using all elements in input number list.So each permutation will have the length of input list.

Example

For numbers [1,2,3] the unique permutations are:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Logical Steps

1. Create an recursive helper function to take current number add into list. Add list into result when list length = nums length (since all permutation have same length)
2. Add element into list in a loop. Check if current number is already in the list, if yes, skip.
3. Bring current list and result into next level of recursion
4. Backtrack and remove the last element in the list

Code Template

// define helper
public void helper(nums, rst, list) {
    // base case: add list into rst
    if (list.size() == rst.size()) {
        rst.add(new ArrayList<Integer>(list));

        // return and stop adding more number into list
        return;
    }

    // add elements into list in a loop
    for (int i=0; i<nums.size(); i++) {
        /**
        * if current element already in list
        * dont add it into list
        */
        if (list.contains(nums.get(i)))
            continue;

        list.add(nums.get(i));
        helper(nums, rst, list);

        // remove last element in list and look for 
        // new element
        list.remove(list.size()-1);
    }
}

Common Mistakes

1. Add list into result without creating a new array list, this will lead to all empty entries in result.
2. Forget to add elements in a loop, that will cause no new element after list elements got removed.

Follow Up: deduplication

If there are duplicate in input elements, make sure each elements appear in result permutations once. (Can have the same value, cannot use the same element).

Logical Steps: deduplication

Use visited to track visited elements, use prev to track prev element (after input sorted)

1. Sort input array before helper to put all duplicate numbers together
2. Skip element under two cases: one, element is already visited; two, element equals to previous element
3. Backtrack: remove last element from the list, and remove visited flag on current element (since all possibilities for current element is in result)

Code Template

    prev = Integer.MIN_VALUE;
    // add elements into list in a loop
    for (int i=0; i<nums.size(); i++) {
        /**
        * Skip under two cases
        * 1. Element is visited before
        * 2. Not visited, but value = previous element
        */
        if (visited[i] == 1 && prev == nums.get(i))
            continue;

        list.add(nums.get(i));
        prev = nums.get(i);
        visited[i] = 1;
        helper(nums, rst, list, visited);

        // remove last element in list
        list.remove(list.size()-1);

        // all permutation for current element is done
        // remove it in visited for next element
        visited[i] = 0;
    }

Common Mistakes: deduplication

1. Create a new visited out during new recursive call