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

# 02/17/2022 46

46\. Permutations

![](https://423021406-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mjjyb1BqScHCWaFFmF4%2Fuploads%2FuCx0pzsVXDohCLsCOA8z%2Fimage.png?alt=media\&token=c817feab-b3bf-4f00-9dae-389bf6347402)

Method:

Use backtracking. Created a boolean array used with the same size of nums. Iterate the elements and if it is not used, add it to the path and mark it as used. If the path's size is the same as the nums.length, then add the path into the result. Noted the difference between permutations and combinations is that the order does matter. So in the for loop in the backtracking function, index i should equal to 0. 

Time O(n \* n!)

Space O(n)? not sure about this.

```
class Solution { 
    List<List> result = new ArrayList<>(); 
    LinkedList path = new LinkedList<>(); 
    boolean [] used; 
    public List<List> permute(int[] nums) { 
        if(nums == null || nums.length == 0) 
        return result; 
        used = new boolean[nums.length]; 
        backtracking(nums); 
        return result;
        }
    private void backtracking(int[] nums){
        if(path.size() == nums.length){
            result.add(new ArrayList(path));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            if(used[i] == true) continue;
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums);
            path.removeLast();
            used[i] = false;
        }
    }
```

}

I think it is`n * n!` because you have n numbers and each number you have called n! times for backtrack dfs function. System stack also takes `n * n!` backtrack dfs functions in total. Thus, both time and space complexity is `O(n * n!)`.

Given n = 3, the number of elements and nums = \[1,2,3]. First element \[1]: 6 backtrack calls = 3 \* 2 \* 1 = 3! = n! Second element \[2]: 6 backtrack calls = 3 \* 2 \* 1 = 3! = n! Third element \[3]: 6 backtrack calls = 3 \* 2 \* 1 = 3! = n! Thus, 3 (the number of elements \[1,2,3]) \* 3! = n (the number of elements) \* n! -> O(n \* n!)

temp: \[1] -(bt\_a.1)-> \[1,2] -(bt\_a.2)-> \[1,2,3] -(bt\_a.3)-> ans: \[\[1,2,3]] -> temp:\[1,2] -> \[1]&#x20;

temp: \[1] -(bt\_a.4)-> \[1,3] -(bt\_a.5)-> \[1,3,2] -(bt\_a.6)-> ans: \[\[1,2,3], \[1,3,2]] -> temp: \[1,3] -> \[1] -> \[]:&#x20;

temp: \[2] -(bt\_b.1)-> \[2,1] -(bt\_b.2)-> \[2,1,3] -(bt\_b.3)-> ans: \[\[1,2,3], \[1,3,2], \[2,1,3]] -> temp: \[2,1] -> \[2]:&#x20;

temp: \[2] -(bt\_b.4)-> \[2,3] -(bt\_b.5)-> \[2,3,1] -(bt\_b.6)-> ans: \[\[1,2,3], \[1,3,2], \[2,1,3], \[2,3,1]] -> temp: \[2, 3] -> \[2] -> \[]&#x20;

temp: \[3] -(bt\_c.1)-> \[3,1] -(bt\_c.2)-> \[3,1,2] -(bt\_c.3)-> ans: \[\[1,2,3], \[1,3,2], \[2,1,3], \[2,3,1], \[3,1,2]] -> temp: \[3,1] -> \[3]&#x20;

temp: \[3] -(bt\_c.4)-> \[3,2] -(bt\_c.5)-> \[3,2,1] -(bt\_c.6)-> ans: \[\[1,2,3], \[1,3,2], \[2,1,3], \[2,3,1], \[3,1,2], \[3,2,1]] -> temp: \[3,2] -> \[3] -> \[3]