# 46 Leetcode Permutation I

Problem name: Permutation I

• problem url:https ://leetcode.com/problems/permutations/

Problem definition:

- Input: nums
- Output: return all the possible permutation.

Approaching:

D-space									[1, 2, 3]
                    
D-space = 		  [1]					  [2]				 [3]	
C = 			[2, 3]				  	[1, 3]			   [1, 2]


D-space = [1, 2]   [1, 3]			[2, 1]   [2, 3]    [3, 1]  [3, 2]
C =        [3] 		[2]				  [3]	  [1]		 [2]     [1] 


if D-space[i]'s length is eqaul with nums.lengh, push the path's Array into result array.

Code

	var permute = function(nums){
     	const res = []
   	function bt(used, path){
         if (path.length === nums.length){
         	res.push([...path])
         }
         
         for(let i = 0; i < nums.length; i++){
           let candidate = nums[i];
           if (used[i]) conitnue;
         	
           used[i] = true;
           path.push(used, path)
           
           used[i] = false;
           path.pop()
       }
     }
     return res
   }

TimeComplexity

o(n!)

Summary

• Using backtracking, we try all the possible number and build permutation.
• By using "used" Array, check number if it is visited or not.
• Completed permutation (path.length === nums.length) push into the result.
• The total number of permutations is n!.