未分類

Combination Sum II

Array, Backtracking, Go, LeetCode

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example:

1
2
3
4
5
6
7
8
Given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
提示 解題應用
Array Array/Slice
Backtracking Recursive

Default:

1
2
3
func combinationSum2(candidates []int, target int) [][]int {
}

解答思路:

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

一開始一樣先做排序以減少不必要的組合，接下來就是不斷的將現有組合做遞回直到找出所有可能為止，與前一題不同的是這次會出現重覆值，而且每個值最多只能取一次不行再取自身的值，所以在開始做遞回後的過程中如果現階段的總合比目標值小，要繼繼將目前組合與取出的元素再次做組合之前，如果該元素與前一次取出相同就跳過，如此一來便不會再出現相同的組合結果，就算陣列元素出現重覆值最後也能找出不重覆為目標值總合的所有組合。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，如果總合比目標值小要繼繼將目前組合與取出的元素再次做組合之前，如果該元素的index大於0且與前一次取出的元素相同就跳過，並再為下一次遞回做準備而帶入參數時，注意這次待被組合的元素陣列candidates要從下一個元素開始，因為這次每個值最多只能取一次不行再取自身的值，最後一樣待找出所有組合才再次向上回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func combine(sum int, target int, curComb []int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if sum == target {
		...
	} else if sum < target {
		for i, v := range candidates {
			if i > 0 && v == candidates[i-1] {
				continue
			}
			tmp = combine(sum+v, target, append(curComb, v), candidates[i+1:])
			result = append(result, tmp...)
		}
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	return combine(0, target, []int{}, candidates)
}
func combine(sum int, target int, curComb []int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if sum == target {
		tmpCurComb := make([]int, len(curComb))
		copy(tmpCurComb, curComb)
		return [][]int{tmpCurComb}
	} else if sum < target {
		for i, v := range candidates {
			if i > 0 && v == candidates[i-1] {
				continue
			}
			tmp = combine(sum+v, target, append(curComb, v), candidates[i+1:])
			result = append(result, tmp...)
		}
	}
	return result
}

總結:

建議可以先參考先前Combination Sum的解法，解說較為詳細，基本上概念完全一樣，只是這次會出現重覆值，而且每個值最多只能取一次不行再取自身的值，所以如果取出的元素與前一次相同就跳過，如此一來便不會再出現相同的組合結果，就算陣列元素出現重覆值最後也能找出不重覆為目標值總合的所有組合。

分享到