package main

func nextPermutation(nums []int) {
	if len(nums) < 2 {
		return
	}
	// rfind first num descended 'ni'
	// 346987521 -> 34 '6' 987521
	i := len(nums) - 2
	for ; i >= 0 && nums[i] >= nums[i+1]; i-- {
	}
	if i != -1 {
		// find the last num 'nj' which is larger than 'ni'
		// swap 'nj', 'ni'
		// 34 '6' 987521 -> 34 '6' 98 '7' 521 -> 34 '7' 98 '6' 521
		j := i + 1
		for ; j+1 < len(nums) && nums[j+1] > nums[i]; j++ {
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	// reverse the sequence after pos 'i'
	// 34 '7' '986521' -> 34 '7' '125689'
	for l, r := i+1, len(nums)-1; l < r; l, r = l+1, r-1 {
		nums[l], nums[r] = nums[r], nums[l]
	}
}

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	cnt := 1
	for i := 2; i <= len(nums); i++ {
		cnt *= i
	}
	res := [][]int{nums}
	last := make([]int, len(nums))
	copy(last, nums)
	for i := 0; i < cnt-1; i++ {
		solution := make([]int, len(last))
		copy(solution, last)
		nextPermutation(solution)
		copy(last, solution)
		res = append(res, solution)
	}
	return res
}

/* func main() {
	a1 := []int{1, 2, 3}
	fmt.Println(permute(a1))
}
*/