未分類

Permutations II

Backtracking, Go, LeetCode

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example:

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

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

Default:

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

解答思路:

建議可以先參考先前Permutations的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果在陣列元素不重覆的情況下可以找出所有組合，當然出現陣列元素會重覆的可能要篩選掉相同的組合就簡單多了。

一開始先做排序以利後續找出重覆的值，接下來就是不斷的將現有組合做遞回直到找出所有可能為止，與前一題不同的是這次會出現重覆值，所以在開始做遞回後的過程中如果被搭配的陣列長度不為0，要繼繼將目前組合與取出的元素再次做組合之前，如果該元素與前一次取出相同就跳過，待搭配的陣列一樣是重新組合原陣列且不包含取出的自身元素，如此一來便不會出現相同的組合結果，就算陣列元素出現重覆值最後也能找出不重覆的所有組合。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，因為陣列會出現重覆值而且要篩選掉相同的組合，所以一開始就先做排序以利後續找出重覆的值

1
2
3
4
func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	return recursive([]int{}, nums)
}

至於要繼繼將目前組合與取出的元素再次做組合之前，如果該元素的index大於0且與前一次取出的元素相同就跳過，最後一樣待迴圈結束找出所有結果組合才向上回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func recursive(cur []int, nums []int) [][]int {
	var new []int
	var tmp [][]int
	var result [][]int
	if len(nums) == 0 {
		...
	}
	for i, v := range nums {
		if i > 0 && v == nums[i-1] {
			continue
		}
		...
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	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 {
		if i > 0 && v == nums[i-1] {
			continue
		}
		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
}

總結:

建議可以先參考先前Permutations的解法，解說較為詳細，基本上概念完全一樣，只是這次陣列會出現重覆值，如果取出的元素與前一次相同就跳過，待搭配的陣列一樣是重新組合原陣列且不包含取出的自身元素，如此一來便不會出現相同的組合結果，就算陣列元素出現重覆值最後也能找出不重覆的所有組合。

分享到