46. Permutations

Medium (LinkedIn, Microsoft)

Given a collection of distinct 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], [3,2,1]

]

public class Solution {

// test case:
// nums is empty

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    if(nums == null || nums.length == 0) {
        return ans;
    }

    boolean[] visited = new boolean[nums.length];
    backtrack(ans, new ArrayList<Integer>(), nums, visited);
    return ans;
}

public void backtrack(List<List<Integer>> ans, List<Integer> list, int[] nums, boolean[] visited) {
    if(list.size() == nums.length) {
        ans.add(new ArrayList<Integer>(list));
        return ;
    }

    for(int i = 0; i < nums.length; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            list.add(nums[i]);
            backtrack(ans, list, nums, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

}

47. Permutations II

Medium (LinkedIn, Microsoft)

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], [2,1,1]

]

Explaination:

Array nums should be sorted first

public class Solution {

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    if(nums == null || nums.length == 0) {
        return ans;
    }

    boolean[] visited = new boolean[nums.length];
    Arrays.sort(nums);
    backtrack(ans, new ArrayList<Integer>(), nums, visited);
    return ans;
}

public void backtrack(List<List<Integer>> ans, List<Integer> list, int[] nums, boolean[] visited) {
    if(list.size() == nums.length) {
        ans.add(new ArrayList<Integer>(list));
        return ;
    }

    for(int i = 0; i < nums.length; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            list.add(nums[i]);
            backtrack(ans, list, nums, visited);
            list.remove(list.size() - 1);
            visited[i] = false;

            // 重复部分需要写在 visited[i] == false里
            // 表示当此element被选上时，才跳过相同的element
            while(i + 1 < nums.length && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    }
}

}