LeetCode - Permutations

https://leetcode.com/problems/permutations

Problem

Given an array nums of distinct integers, return all the possible permutations

Solution

There are not too much things to say about this problem, it’s a basic recursive problem.

There are a lot of implementation, i will go with the most basic one. We will try to build all permutations, from left (index 0) to right (index len-1). For each position i, we will pick an “available number” from the given array. An available number is a number that hasn’t been used to build the current permutation from index 0 to position i-1.

Since the array contains distinct integers, we don’t need to care about duplicated permutations.

This is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func permute(nums []int) [][]int {
used := make([]bool, len(nums))
result := make([][]int, 0)
curArray := make([]int, 0)
generate(nums, used, curArray, 0, &result)
return result
}

func generate(nums []int, used []bool, curArray []int, idx int, result *[][]int) {
if idx == len(nums) {
// Make sure to put a cloned array
nextResult := append([]int(nil), curArray...)
*result = append(*result, nextResult)
return
}
for i, v := range nums {
// Choose an available number to append to current array
if !used[i] {
used[i] = true
curArray = append(curArray, v)
generate(nums, used, curArray, idx+1, result)
curArray = curArray[:len(curArray)-1]
used[i] = false
}
}
}

Time complexity is O(N!) and also Memory complexity is O(N!)


Support me via: https://ko-fi.com/iamquang95