Permutations

题目地址：
https://leetcode.com/problems/permutations/description/

题目：

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]
]

解题思路：
这道题就直接运用dfs加上list去重就可以。

代码：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    if(nums == null || nums.length == 0){
        return rst;
    }
    List<Integer> list = new ArrayList<>();
    dfs(nums, rst, list);
    return rst;
}

private void dfs(int[] nums, List<List<Integer>> rst, List<Integer> list){
    if(list.size() == nums.length){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = 0; i <= nums.length - 1; i++){
        if(list.contains(nums[i])){
            continue;
        }
        list.add(nums[i]);
        dfs(nums, rst, list);
        list.remove(list.size() - 1);
    }
};

Follow up:
Link: https://leetcode.com/problems/permutations-ii/description/

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]
]

这里可以用一个set来根据index去重。

代码：

public static void main(String[] args){
    Permutations permutations = new Permutations();
    int[] nums = {1, 1, 2};
    List<List<Integer>> rst = permutations.permuteUnique(nums);
    System.out.println(rst);
}

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    if(nums == null || nums.length == 0){
        return rst;
    }
    Arrays.sort(nums);
    List<Integer> list = new ArrayList<>();
    Set<Integer> set = new HashSet<>(); // set contains all the index that I have added    dfs(nums, rst, list, set);
    return rst;
}

private void dfs(int[] nums, List<List<Integer>> rst, List<Integer> list, Set<Integer> set){
    if(list.size() == nums.length){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = 0; i <= nums.length - 1; i++){
        if(i != 0 && nums[i - 1] == nums[i] && !set.contains(i - 1)){
            continue;
        }
        if(set.contains(i)){
            continue;
        }
        set.add(i);
        list.add(nums[i]);
        dfs(nums, rst, list, set);
        list.remove(list.size() - 1);
        set.remove(i);
    }
}