未分類

Permutations

Backtracking, Go, LeetCode

Permutations

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

For example:

[1,2,3] have the following permutations:

1
2
3
4
5
6
7
8
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
提示 解題應用
Backtracking Recursive

Default:

1
2
3
func permute(nums []int) [][]int {
}

解答思路:

這題基本上就是要用遞回來處理以獲得所有組合，重點在於用迴圈從陣列取出元素並要在向下再次遞回前，要將還要用來再次組合的陣列移出目前取出的元素，以避免重覆組合到自身元素，這邊我的做法是重新組合要向下遞回的陣列，也就是該元素之前的所有元素與該元素之後的所有元素重新組合成新的陣列，如此一來在遞回結束後就可以獲得所有想要的組合並且不會重覆出現自身的元素。

程式碼解說:

一開始便將值帶入遞回之間以找出所有組合，其中第一個參數陣列為目前陣列的組合，而第二個參數陣列則是要與目前陣列組合搭配出新組合的選項

1
2
3
func permute(nums []int) [][]int {
	return recursive([]int{}, nums)
}

一開始先判斷如果要被搭配的陣列長度為0，此時就回傳目前現有的陣列組合，這部分是先新增一個空陣列再將目前的組合一一複製過去才回傳，至於為什麼這麼做而不是直接回傳目前的組合，理由與slice的特性有關，最初我也是誤解其特性，所幸stackoverflow有人解答幫助我理解，可以參考Combination Sum in Go，而如果被搭配的陣列不為空，則繼繼將目前組合與要被搭配的陣列再次做組合並放入遞回中，至於新的待搭配陣列則是重新組合原陣列且不包含取出的自身元素，待最後迴圈結束找出所有結果組合才向上回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func recursive(cur []int, nums []int) [][]int {
	var new []int
	var tmp [][]int
	var result [][]int
	if len(nums) == 0 {
		tmpCur := make([]int, len(cur))
		copy(tmpCur, cur)
		return [][]int{tmpCur}
	}
	for i, v := range nums {
		new = append(new, nums[:i]...)
		new = append(new, nums[i+1:]...)
		tmp = recursive(append(cur, v), new)
		result = append(result, tmp...)
		new = []int{}
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func permute(nums []int) [][]int {
	return recursive([]int{}, nums)
}
func recursive(cur []int, nums []int) [][]int {
	var new []int
	var tmp [][]int
	var result [][]int
	if len(nums) == 0 {
		tmpCur := make([]int, len(cur))
		copy(tmpCur, cur)
		return [][]int{tmpCur}
	}
	for i, v := range nums {
		new = append(new, nums[:i]...)
		new = append(new, nums[i+1:]...)
		tmp = recursive(append(cur, v), new)
		result = append(result, tmp...)
		new = []int{}
	}
	return result
}

總結:

給一陣列其元素間不會出現重覆值，找出元素值在不同位置上的所有組合，而基本上就是要用遞回來處理以獲得所有組合，重點在於用迴圈從陣列取出元素並要在向下再次遞回前，要將還要用來再次組合的陣列移出目前取出的元素，以避免重覆組合到自身元素，這邊我的做法是重新組合要向下遞回的陣列，也就是該元素之前的所有元素與該元素之後的所有元素重新組合成新的陣列，如此一來在遞回結束後就可以獲得所有想要的組合並且不會重覆出現自身的元素。

分享到