Permutations

1. Problem Description

Given a sequence of distinct numbers, return all possible permutations.

2. Approach

1. Approach 1
   • The element at index can be swapped with any later element
   • Continue with index+1
   • Backtrack by swapping the element at index back
2. Approach 2
   • DFS: each position can use any of the len(num) numbers
   • Use a set to record numbers already used
   • Remember to backtrack after visiting

3. Implementation

3.1. Swap

package main

import "sort"

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}

	res := make([][]int, 0)
	permutes(nums, 0, &res)
	sort.Slice(res, func(i, j int) bool {
		a := res[i]
		b := res[j]

		for i := 0; i < len(a); i++ {
			if a[i] == b[i] {
				continue
			}else if a[i] < b[i] {
				return true
			}else {
				return false
			}
		}

		return true

	})

	return res
}

func permutes(nums []int, index int, res *[][]int) {
	if index == len(nums)-1 {
		dst := make([]int, len(nums), len(nums))
		copy(dst, nums)
		*res = append(*res, dst)
		return
	}

	for i := index; i < len(nums); i++ {
		swap(nums, i, index)

		permutes(nums, index+1, res)

		swap(nums, i, index)

	}
}

3.2. Backtracking

func permute(nums []int) [][]int {
	var res [][]int
	path := make([]int, 0, len(nums))
	permuteDFS(nums,  &path, &res)
	return res
}

func permuteDFS(nums []int, path *[]int, res *[][]int) {
	// Unlike subsets, add to res only when the length reaches len
	if len(*path) == len(nums) {
		dst := make([]int, len(*path))
		copy(dst, *path)
		*res = append(*res, dst)
		return
	}

	// Unlike subsets, start from 0
	for i := 0;i < len(nums); i++{
		if visited(path, nums[i]) {
			continue
		}
		*path = append(*path, nums[i])
		permuteDFS(nums, path, res)
		*path = (*path)[:len(*path)-1]
	}
}

func visited(path *[]int, target int) bool {
	for _, num := range *path {
		if num == target {
			return true
		}
	}
	return false
}

4. References

• 46. Permutations - LeetCode