46. Permutations

三刷 06/2022

Version #1 DFS with visited map

Time O(N*N!)

Space O(N)

Runtime: 4 ms, faster than 19.36% of Java online submissions for Permutations.

Memory Usage: 43.9 MB, less than 72.08% of Java online submissions for Permutations.

class Solution {

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

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {

            return result;

        }

        // In each layer we must select a number

        // We collect the result until all layers have selected numbers

        dfs(nums, new ArrayList<>(), new HashSet<>(), result);

        return result;

    }

    private void dfs(int[] nums, List<Integer> path, Set<Integer> visited, List<List<Integer>> result) {

        if (path.size() == nums.length) {

            result.add(new ArrayList<>(path));

            return;

        }

        for (int num : nums) {

            if (visited.contains(num)) {

                continue;

            }

            visited.add(num);

            path.add(num);

            dfs(nums, path, visited, result);

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

            visited.remove(num);

        }

    }

}

Version #2 DFS backtracking with swaping

这里主要是swap之后要做backtracking

Time O(N * N!)

Space O(N) - for recursion stack

Runtime: 7 ms, faster than 6.41% of Java online submissions for Permutations.

Memory Usage: 44.9 MB, less than 37.90% of Java online submissions for Permutations.

class Solution {

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

        List<List<Integer>> result = new ArrayList<>();

        dfs(nums, 0, result);

        return result;

    }

    

    private void dfs(int[] nums, int startIndex, List<List<Integer>> result) {

        if (startIndex == nums.length - 1) {

            result.add(Arrays.stream(nums).boxed().toList());

            return;

        }

        for (int i = startIndex; i < nums.length; i++) {

            swap(nums, startIndex, i);

            dfs(nums, startIndex + 1, result);

            swap(nums, startIndex, i);

        }

    }

    private void swap(int[] nums, int p, int q) {

        int temp = nums[p];

        nums[p] = nums[q];

        nums[q] = temp;

    }

}

二刷
完全不一样的版本
一刷是swap version
The recursive solution has a complexity of O(n!) as it is governed by the equation: T(n) = n * T(n-1) + O(1)
75.54 %
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        boolean[] used = new boolean[nums.length];
        helper(nums, used, new ArrayList<>(), result);
        return result;
    }
    private void helper(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
        boolean hasUnusedValue = false;
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                hasUnusedValue = true;
                used[i] = true;
                path.add(nums[i]);
                helper(nums, used, path, result);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
        if (!hasUnusedValue) {
            result.add(new ArrayList<>(path));
        }
    }
}

一刷
Today, when I'm trying to solve this problem, I found a very confused compile error. It is something about polymorphism in Java.
http://docs.oracle.com/javase/1.5.0/docs/guide/language/generics.html
http://docs.oracle.com/javase/tutorial/java/generics/index.html

这道题的思路是，每次选定一个位置，和自己或者和这个位置之后的任意位置swap
下一次进行到下一个位置
譬如（1， 2， 3）

level1        1,2,3                 2,1,3              3,2,1
level2    1,(2,3)   1,(3,2)     2,(1,3)  2,(3,1)     3,(2,1)   3,(1,2)
level3    1,2,(3)
level4
进行到level3的时候因为只和自己swap不会改变结果，所以可以提前一层就返回

这里我自己写出一个bug想了好一会儿，是在recursivcly调用helper的时候
一般都是 helper(nums, index + 1, result);
但是这道题是 helper(nums, startIndex + 1, result);

这个意思是说
             startIndex              index
       1,         2,          3,          4,          5,            6,  ...
因为每一层确定一个Position的数，所以下一层应该确定下一个position 也就是startIndex + 1
而其他题一般是选取数字，为了防止重复所以只选择当前数字右边的数
犯这个错误还是因为对题目理解的不够深刻

58.84%

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return result;
        helper(nums, 0, result);
        return result;
    }
    public void helper(int[] nums, int startIndex, List<List<Integer>> result) {
        if (startIndex == nums.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int i : nums) list.add(i);
            result.add(list);
            return;
        }
        //can swap with it self
        for (int index = startIndex; index < nums.length; index++) {
            swap(nums, startIndex, index);
            helper(nums, startIndex + 1, result);
            //swap back, backtracking
            swap(nums, startIndex, index);
        }
    }
    public void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) return;
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}