46. Permutations

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和Backtracking。 原理是从0到数组长度N，每次对之前加入的元素进行回溯。 注意此解法假定输入数组之中没有重复元素。
Time Complexity - O(n!)， Space Complexity - O(n)。
注意：如果是有和无的关系用到DFS，则每次递归时有position，这种全排列的情况，每次递归，index从0到length-1

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length==0) return res;
        
        permulate(nums, res, new ArrayList<Integer>());
        return res;
    }
    
    
    void permulate(int[] nums, List<List<Integer>> res,  List<Integer> list){
        if(list.size() == nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if(list.contains(nums[i])) continue;
            list.add(nums[i]);
            permulate(nums, res, list);
            list.remove(list.size()-1);
        }
    }
}

注意，这种方法的缺点是，contains的方法调用一次时间复杂度为O(n)，可以尝试用hashSet改进

方法二， 用boolean数组记录元素是否被访问

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length==0) return res;
        
        boolean[] visited = new boolean[nums.length];
        permulate(nums, res, new ArrayList<Integer>(), visited);
        return res;
    }
    
    
    void permulate(int[] nums, List<List<Integer>> res,  List<Integer> list, boolean[] visited){
        if(list.size() == nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            list.add(nums[i]);
            permulate(nums, res, list, visited);
            list.remove(list.size()-1);
            visited[i] = false;
        }
    }
}

二刷时可以用next permutation的方法

二刷：
注意，题目的特点是without dup， 且每次扫描元素都从头开始。所以我们可以用list.contains来判断是否应该加入。

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        permute(res, list, nums);
        return res;
    }
    
    private void permute( List<List<Integer>> res, List<Integer> list,
                        int[] nums){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if(list.contains(nums[i])) continue;
            list.add(nums[i]);
            permute(res, list, nums);
            list.remove(list.size()-1);
        }
    }
}