> For the complete documentation index, see [llms.txt](https://tonyding.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tonyding.gitbook.io/algorithm/lc-46-permutations.md).

# LC 46 Permutations(M)

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

## 解题思路 采用Recursive

方法1 路是采用逐一向中间集添加元素，并将当中间集元素个数等于 nums 长度的时候，将中间集添加到结果集中，并终止该层递归

```java
public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      //依次把值放入 tempList,如果已经有，就跳过
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         //一旦有新值放入，递归循环到下一个长度
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         //删除最后的值，看能不继续加新的值
         tempList.remove(tempList.size() - 1);
      }
   }
}
Code flow
1 -> 1,2 -> 1,2,3 
     1,3 -> 1,3,2
2 -> 2,1 -> 2,1,3
     2,3 -> 2,3,1
3 -> 3,1 -> 3,1,2
     3,2 -> 3,2,1
```

方法2 当n=1时，数组中只有一个数a1，其全排列只有一种，即为a1

当n=2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2

当n=3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。

```java
public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> permutations = new ArrayList<>();
   if (nums.length == 0) {
      return permutations;
   }   
   collectPermutations(nums, 0, new ArrayList<>(), permutations);
   return permutations;
}

private void collectPermutations(int[] nums, int start, List<Integer> permutation, List<List<Integer>>  permutations) {    
   if (permutation.size() == nums.length) {
      permutations.add(permutation);
      return;
   }
   for (int i = 0; i <= permutation.size(); i++) {
      // 用传进来的 排列重构一个新的临时排列
      List<Integer> newPermutation = new ArrayList<>(permutation);
      // 分别把新的nums[start] 插入 临时排列的每个位置（0， permutation.size，
      newPermutation.add(i, nums[start]);
      // 每插一个位置 递归循环到下一个长度。
      collectPermutations(nums, start + 1, newPermutation, permutations);
   }
}
code flow
1-> 2,1 -> 3,2,1 | 2,3,1 | 2,1,3
    1,2 -> 3,1,2 | 1,3,1 | 1,2,3
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tonyding.gitbook.io/algorithm/lc-46-permutations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.