未分類

Combination Sum

Array, Backtracking, Go, LeetCode

Combination Sum

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

The same repeated number may be chosen from C unlimited number of times.

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
Given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]
提示 解題應用
Array Array/Slice
Backtracking Recursive

Default:

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

解答思路:

從先前解題的經驗來看(2Sum,3Sum…)，通常要找出總合的全部組合是相當複雜的一件事，所以要降低複雜難度的方式就是先將需要被組合的元素陣列做排序，如此一來當加入元素後的總合比目標值大時，就可以不必再去嘗試後頭更大的元素，而因為要被組合的陣列中沒有重覆的值，再加上也沒有規定必須要由多少個值組成總合，因此必須要盡可能將所有長度的組合都試一遍，所以就是不斷的將現有組合做遞回直到找出所有可能為止。

程式碼解說:

如先前所提，為了減少不必要的組合，在遞回之前先將需要被組合的元素陣列做排序，完成排序後就將目前的總合(一開始為0)、目標總合、目前的組合(一開始為空)及要被組合的元素陣列帶入function並開始遞回

1
2
3
4
func combinationSum(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	return combine(0, target, []int{}, candidates)
}

接下來便是遞回內容的重點，如果總合為目標值就將目前的組合回傳，這部分是先新增一個空陣列再將目前的組合一一複製過去才回傳，至於為什麼這麼做而不是直接回傳目前的組合，理由與slice的特性有關，最初我也是誤解其特性，所幸stackoverflow有人解答幫助我理解，可以參考Combination Sum in Go，而如果總合比目標值小則繼繼將目前組合與元素自身及其後頭的元素再次做組合，並將每次得到的回傳放入結果之中，待找出所有組合最後才再次向上回傳，最後如果是總合大於目標值的情況則會回傳一個空的二元陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 {
			tmp = combine(sum+v, target, append(curComb, v), candidates[i:])
			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
func combinationSum(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 {
			tmp = combine(sum+v, target, append(curComb, v), candidates[i:])
			result = append(result, tmp...)
		}
	}
	return result
}

總結:

一陣列中不包含重覆值，要找出目標總合的所有組合(沒有規定一定要由多少個值組成)，必須要盡可能將所有長度的組合都試一遍，所以就是不斷的將現有組合做遞回直到找出所有可能為止，而為了減少不必要的組合，在遞回之前先將需要被組合的元素陣列做排序，如此一來當加入元素後的總合比目標值大時，就可以不必再去嘗試後頭更大的元素。

分享到