未分類

Subsets II

Array, Backtracking, Go, LeetCode

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

The solution set must not contain duplicate subsets.

For example:

If nums = [1,2,2], a solution is:

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

Default:

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

解答思路:

建議可以先參考先前Subsets的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍作修改而已，如果之前在元素不重覆的情況下能找出陣列中長度0~n的所有組合，那麼現在在元素重覆的情況下要篩選掉相同的組合就不會太困難。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，一開始最主要是先做排序，排序的主要目地就是要讓相同的元素能鄰近在一起，如此一來在取出的元素時，發現和前一個所取出的元素相同就跳過

1
2
3
4
func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	...
}

接下來就是在取出元素並與現階段已組合好的陣列再次做組合之前，判斷index值是否大於0，並且如果發現目前所取出的元素和前一個所取出的元素相同就跳過，最後就不會在結果之中發現相同的組合

1
2
3
4
5
6
7
8
9
10
func recursive(curComb []int, k int, candidates []int) [][]int {
	...
	for i, v := range candidates {
		if i > 0 && v == candidates[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
26
27
28
29
30
func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	var tmp [][]int
	var result [][]int
	for i := 0; i <= len(nums); i++ {
		tmp = combine(nums, i)
		result = append(result, tmp...)
	}
	return result
}
func combine(nums []int, k int) [][]int {
	return recursive([]int{}, k, nums)
}
func recursive(curComb []int, k int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if len(curComb) == k {
		tmpCurComb := make([]int, len(curComb))
		copy(tmpCurComb, curComb)
		return [][]int{tmpCurComb}
	}
	for i, v := range candidates {
		if i > 0 && v == candidates[i-1] {
			continue
		}
		tmp = recursive(append(curComb, v), k, candidates[i+1:])
		result = append(result, tmp...)
	}
	return result
}

總結:

建議可以先參考先前Subsets的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍作修改而已，現在在元素重覆的情況下要篩選掉相同組合的話，基本上就是先做排序，排序的主要目地就是要讓相同的元素能鄰近在一起，接下來就只要在取出元素以再次做組合時，如果發現現在取出的元素和前一個所取出的元素相同就跳過，如此一來最後就不會出現相同的組合結果。

分享到