> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/permutations.md).

# 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).