[LeetCode] Permutations and Permutations II (Java)

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Analysis

It’s easy to implement Permutation recursively. In every level we use a for loop to pick any entry in the array, delete it from the array, and then do this recursively until the array is empty. Now we have a permutation and add it to the result list.

In Permutations, we are asked to generate permutations for an array, in which there is no duplicates. But in Permutation II, the array might contains duplicates, so that if we use the code that can pass Permutations, it may generate some duplicate results, which is not allowed in this problem. We can check if the previous one is also the same value as the number we are going to put it in the permutation list. If it’s in the permutation list and the value is equal, we won’t put it in the list. We use an boolean array to save the visit status. ArrayList is also used here because we usually need to visit certain element by index.

Code

Permutations

public class Solution {
    List<List<Integer>> ret;
    public List<List<Integer>> permute(int[] num) {
        ret = new LinkedList<>();
        LinkedList<Integer> numbers = new LinkedList<>();
        for (int i = 0; i < num.length; i++)
            numbers.add(num[i]);
        LinkedList<Integer> list = new LinkedList<>();
        permute(numbers, list);
        return ret;
    }
    
    private void permute(List<Integer> numbers, List<Integer> list) {
        if (numbers.size() == 0) {
            LinkedList<Integer> newList = new LinkedList<>();
            newList.addAll(list);
            ret.add(newList);
            return;
        }
        for (int i = 0; i < numbers.size(); i++) {
            int candidate = numbers.get(i);
            numbers.remove(i);
            list.add(candidate);
            permute(numbers, list);
            list.remove(list.size() - 1);
            numbers.add(i, candidate);
        }
    }
}

public class Solution {

List<List<Integer>> ret;

public List<List<Integer>> permute(int[] num) {

ret = new LinkedList<>();

LinkedList<Integer> numbers = new LinkedList<>();

for (int i = 0; i < num.length; i++)

numbers.add(num[i]);

LinkedList<Integer> list = new LinkedList<>();

permute(numbers, list);

return ret;

}

private void permute(List<Integer> numbers, List<Integer> list) {

if (numbers.size() == 0) {

LinkedList<Integer> newList = new LinkedList<>();

newList.addAll(list);

ret.add(newList);

return;

}

for (int i = 0; i < numbers.size(); i++) {

int candidate = numbers.get(i);

numbers.remove(i);

list.add(candidate);

permute(numbers, list);

list.remove(list.size() - 1);

numbers.add(i, candidate);

}

Permutations II

public class Solution {
    List<List<Integer>> ret;
    public List<List<Integer>> permuteUnique(int[] num) {
        ret = new LinkedList<>();
        Arrays.sort(num);
        ArrayList<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < num.length; i++)
            numbers.add(num[i]);
        boolean[] visited = new boolean[num.length];
        LinkedList<Integer> list = new LinkedList<>();
        permuteUnique(numbers, list, visited);
        return ret;
    }

    private void permuteUnique(List<Integer> numbers, List<Integer> list, boolean[] visited) {
        if (list.size() == numbers.size()) {
            LinkedList<Integer> newList = new LinkedList<>();
            newList.addAll(list);
            ret.add(newList);
            return;
        }
        for (int i = 0; i < numbers.size(); i++) {
            if (visited[i])
                continue;
            int candidate = numbers.get(i);
            if (i > 0 && numbers.get(i - 1) == candidate && visited[i - 1])
                continue;
            visited[i] = true;
            list.add(candidate);
            permuteUnique(numbers, list, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

public class Solution {

List<List<Integer>> ret;

public List<List<Integer>> permuteUnique(int[] num) {

ret = new LinkedList<>();

Arrays.sort(num);

ArrayList<Integer> numbers = new ArrayList<>();

for (int i = 0; i < num.length; i++)

numbers.add(num[i]);

boolean[] visited = new boolean[num.length];

LinkedList<Integer> list = new LinkedList<>();

permuteUnique(numbers, list, visited);

return ret;

}

private void permuteUnique(List<Integer> numbers, List<Integer> list, boolean[] visited) {

if (list.size() == numbers.size()) {

LinkedList<Integer> newList = new LinkedList<>();

newList.addAll(list);

ret.add(newList);

return;

}

for (int i = 0; i < numbers.size(); i++) {

if (visited[i])

continue;

int candidate = numbers.get(i);

if (i > 0 && numbers.get(i - 1) == candidate && visited[i - 1])

continue;

visited[i] = true;

list.add(candidate);

permuteUnique(numbers, list, visited);

list.remove(list.size() - 1);

visited[i] = false;

}

Complexity

We need to generate all permutations. So the complexity is O(n!).