Permutations

https://leetcode.com/problems/permutations/description/

Given a collection of distinct numbers, return all possible permutations.

Thoughts

和subsets的区别在于这次是permutation, [1, 2, 3]和[2, 1, 3]都是合理的答案, 因此不再需要start pos. 但为了防止出现[1, 1, 1,]这样的答案, 还需要用一个set记录当前path已经访问过了谁.

Code

class Solution {
    private void helper(int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            path.add(nums[i]);
            helper(nums, visited, path, res);
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }
}

Analysis

时间复杂度O(N!). 指数级. 空间O(N).