Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Explainer :

Let’s start with three characters ABC. We start with the first character. Start by swapping A with the other characters. A is swapped with A, A is swapped with B and A is swapped with C. We get the following values ABC, BAC and CBA

Once A is finished. Let’s take this string ABC. Get the next character B. We need to swap B with B and B with C. Since A is already swapped. We get ABC and ACB. We reach the end of the tree level, which is three. Always the height of the tree equals the number of elements in the string.

Once we have swapped everything, lets go back and start swapping other characters.

Implementation is here

	var newArray = [[Int]]()
	func permute(_ str: [Int]) -> [[Int]] {
		var nums = str
		findPermutation(&nums, left: 0, right: str.count)
		return newArray
	}
	
	func findPermutation(_ num: inout [Int], left: Int, right: Int) {
		if left == right {
			newArray.append(num)
		}
		for i in left ..< right {
			num.swapAt(i, left)
			findPermutation(&num, left: left+1, right: right)
			num.swapAt(i, left)
		}
	}

let solution = Solution()
var arr = [1,2,3]
print(solution.permute(arr))

Time complexity is O(n*n!)

Space complexity is O(n!)