Thinking process

how to find a permutation?

• starting from the simplest example
  • [1]
  • [1,2]
  • [1,2,3]
  • [1,2,3,4]
• draw a tree

Time complexity

每次函数F(N)中递归调用了N次函数F(N-1)，所以总共有 T(N) =NT(N-1) = N*(N-1) * T(N-2)...T(1)T(0)= N! * T(0) 这么多次函数调用。又因为当每次输入的元素个数N=0时，需要将一个解压入解集。这是一个O(N)操作，也就是T(0) = N, 所以复杂度是O(N!*N)。

http://www.1point3acres.com/bbs/thread-117602-1-1.html

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //validate input
        if (nums.length == 0) return result;
        boolean[] visited = new boolean[nums.length];
        permuteDfsHelper(nums, result, new ArrayList<Integer>(), visited);

        return result;
    }

    private void permuteDfsHelper(int[] nums, List<List<Integer>> result, List<Integer> list, boolean[] visited) {
        //end conditions
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

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

Improve

API Method

list.contains(); => true / false

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //validate input
        if (nums.length == 0) return result;
        permuteDfsHelper(nums, result, new ArrayList<Integer>());

        return result;
    }

    private void permuteDfsHelper(int[] nums, List<List<Integer>> result, List<Integer> list) {
        //end conditions
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            permuteDfsHelper(nums, result, list);
            list.remove(list.size() - 1);
        }
    }
}