> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/dfs/permutation.md).

# Permutation

## 46 Permutation I

Given a list of numbers, return all possible permutations.

* A boolean array to record if used

```python
def permute(self, nums: List[int]) -> List[List[int]]:
    res = []
    visit = [False] * len(nums)
    self.backtrack([], nums, visit, res)
    return res

def backtrack(self, cand, nums, visit, res):
    if len(cand) == len(nums):
        res.append(cand.copy())
        return 
    
    for i in range(len(nums)):
        if visit[i]: continue
        visit[i] = True
        self.backtrack(cand + [nums[i]], nums, visit, res)
        visit[i] = False
```

## 47 Permutation II

Given a list of numbers with duplicate number in it. Find all unique permutations.

* Only traverse the first of duplicate number

```python
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    res = []
    visit = [False] * len(nums)
    nums.sort()
    self.backtrack([], nums, visit, res)
    return res

def backtrack(self, cand, nums, visit, res):
    if len(cand) == len(nums):
        res.append(cand.copy())
        return  
    
    for i in range(len(nums)):
        if visit[i] or (i>0 and nums[i-1] == nums[i] and visit[i-1] == False): continue
        visit[i] = True
        self.backtrack(cand + [nums[i]], nums, visit, res)
        visit[i] = False
```