Решение задачи 46 “Permutations” с LeetCode.

Условие задачи

Дан массив уникальных чисел ( математическое множество) , необходимо вернуть все его возможные перестановки

пример

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

Решение

Рекурсия

Идея алгоритма:

Добавляем фунцию хэлпер, которая на вход принимает начало массива. и массив оставшихся чисел.

Если оставшееся число одно, то добавляем его к началу массива, заворачиваем в массив массивов и возвращаем.

Если оставшихся чисел несколько, то в цикле

• берем текущий элемент
• добавляем его в массиву “начало”
• оставшиемся элементы массива добавляем в временный массив
• вызываем хэлпер передав туда начало массива и оставшиемся элементы
• полученный результат добавляем в массив результатов

возвращаем массив резултатом

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
}