004.排列

• 46.全排列
  • path
  • 数组位置交换
• 47.全排列 II
  • path
  • 数组位置交换

全排列 - path §

var (
	ans [][]int
	path []int
	used []bool
	theNums []int
)
 
func permute(nums []int) [][]int {
	ans = [][]int{}
	path = make([]int, 0, len(nums))
	used = make([]bool, len(nums))
	theNums = nums
 
	backtracking()
 
	return ans
}
 
func backtracking() {
	if len(path) == len(theNums) {
		tmp := make([]int, len(path))
		copy(tmp, path)
		ans = append(ans, tmp)
		return
	}
 
	for i, num := range theNums {
		if used[i] {
			continue
		}
		path = append(path, num)
		used[i] = true
		backtracking()
		used[i] = false
		path = path[:len(path) - 1]
	}
}

全排列 - 数组位置交换 §

var (
	ans     [][]int
	theNums []int
	n       int
)
 
func permute(nums []int) [][]int {
	ans = [][]int{}
	theNums = nums
	n = len(nums)
 
	backtracking(0)
 
	return ans
}
 
func backtracking(idx int) {
	if idx == n {
		tmp := make([]int, n)
		copy(tmp, theNums)
		ans = append(ans, tmp)
		return
	}
 
	for i := idx; i < n; i++ {
		swap(i, idx)
		backtracking(idx + 1)
		swap(i, idx)
	}
}
 
func swap(i, j int) {
	theNums[i], theNums[j] = theNums[j], theNums[i]
}

全排列 II - path §

var (
	ans [][]int
	path []int
	theNums []int
	used []bool
)
 
func permuteUnique(nums []int) [][]int {
	ans = [][]int{}
	size := len(nums)
	if size == 0 {
		return ans
	}
	path = []int{}
	theNums = nums
	sort.Slice(theNums, func(a, b int) bool {
		return theNums[a] <= theNums[b]
	})
	used = make([]bool, size)
 
	backtracking()
 
	return ans
}
 
func backtracking() {
	size := len(theNums)
	if size == len(path) {
		tmp := make([]int, size)
		copy(tmp, path)
		ans = append(ans, tmp)
		return
	}
 
	for i := 0; i < size; i++ {
		if i > 0 && theNums[i] == theNums[i - 1] && !used[i - 1] {
			continue
		}
		if used[i] {
			continue
		}
		used[i] = true
		path = append(path, theNums[i])
		backtracking()
		used[i] = false
		path = path[:len(path) - 1]
	}
}

全排列 II - 数组位置交换 §

var (
	ans         [][]int
	theNums     []int
	n           int
	emptyStruct = struct{}{}
)
 
func permuteUnique(nums []int) [][]int {
	ans = [][]int{}
	theNums = nums
	n = len(nums)
 
	backtracking(0)
 
	return ans
}
 
func backtracking(idx int) {
	if idx == n {
		tmp := make([]int, n)
		copy(tmp, theNums)
		ans = append(ans, tmp)
		return
	}
 
	set := make(map[int]struct{}, n-idx)
	for i := idx; i < n; i++ {
		// theNums[i] 没有来到过 idx 位置，才会去尝试
		// 来过了，说明之前已经收集了相同的答案
		if _, has := set[theNums[i]]; has {
			continue
		}
		set[theNums[i]] = emptyStruct
		swap(i, idx)
		backtracking(idx + 1)
		swap(i, idx)
	}
}
 
func swap(i, j int) {
	theNums[i], theNums[j] = theNums[j], theNums[i]
}