Solution to problem 46 “Permutations” from LeetCode.

Problem Statement

Given an array of unique numbers (a mathematical set), return all its possible permutations.

Example

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

Solution

Recursion

Algorithm idea:

Add a helper function that takes the beginning of the array and an array of remaining numbers as input.

If there is one remaining number, add it to the beginning of the array, wrap it in an array of arrays, and return.

If there are several remaining numbers, then in a loop:

• take the current element
• add it to the “beginning” array
• add the remaining elements of the array to a temporary array
• call the helper passing the beginning of the array and the remaining elements
• add the resulting output to the results array

return the results array

func permute(nums []int) [][]int {
	return helper([]int{}, nums)
}

func helper(firstNums []int, nums []int) [][]int {
	res := make([][]int, 0)
	if len(nums) == 1 {
		f := append(firstNums, nums[0])
		res = append(res, f)
		return res
	}
	for jdx := 0; jdx < len(nums); jdx++ {
		tmp := make([]int, 0, len(nums)-1)
		for kk := 0; kk < len(nums); kk++ {
			if kk != jdx {
				tmp = append(tmp, nums[kk])
			}
		}
		res = append(res, helper(append(firstNums, nums[jdx]), tmp)...)
	}

	return res
}