46.M 全排列

Problem: 46. 全排列

思路

通过交换生成排列。 定义backtrack函数，表示当前要排列start位置：

• 如果start已经达到了数组的末尾，则把当前排列加到返回结果中。

• 否则，从[start, len(nums))区间找一个数与start位置交换。只能从这个区间找是因为[0, start]区间都是已经使用过的数字。

Code

func permute(nums []int) [][]int {
	var ans [][]int
	backtrack(nums, 0, &ans)
	return ans
}

func backtrack(nums []int, start int, ans *[][]int) {
	if start == len(nums)-1 {
		*ans = append(*ans, append([]int{}, nums...))
		return
	}

	// 从start开始，依次交换元素生成排列
	for i := start; i < len(nums); i++ {
		nums[i], nums[start] = nums[start], nums[i]
		backtrack(nums, start+1, ans)
		// 回溯，恢复原始顺序
		nums[i], nums[start] = nums[start], nums[i]
	}
}