Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

提示	解題應用
Backtracking	Recursive

Default:

func combinationSum3(k int, n int) [][]int {

}

解答思路:

建議可以先參考先前Combination Sum的解法，解說較為詳細，基本上概念完全一樣，只是稍微修改先前的程式碼而已，如果能找出數列中符合目標總合的所有組合，現在只要找出特定長度的組合就不會太困難。

這次數列為1~9而且每個只能取1次的情況下，要來找出符合目標總合的所有組合，其實就只要像先前一樣帶入一個包含1~9的陣列與多一個長度限制的參數至遞回函數之中，最後如果發現有符合目標總合且該組合的長度也符合長度限制就將其放入結果陣列，而如果總合小於目標總合則繼續往下做遞回，只是這次有說每個組合的每個值最多只能取一次，因此帶入遞回剩餘未取出的陣列元素不能包含自己的元素。

程式碼解說:

這次數列為1~9而且每個只能取1次的情況下，要來找出符合目標總合的所有組合，其實就只要像先前一樣帶入一個包含1~9的陣列與多一個長度限制的參數至遞回函數之中(遞回函數的第二個參數)

func combinationSum3(k int, n int) [][]int {
	candidates := make([]int, 9)
	for i := 1; i <= 9; i++ {
		candidates[i-1] = i
	}
	return combine(0, k, n, []int{}, candidates)
}

這部分只解說與先前題目程式碼的相異之處，如果發現有符合目標總合且該組合的長度也符合長度限制(能再放入組合的元素數為0)就將其放入結果陣列，而如果總合小於目標總合則繼續往下做遞回(長度限制也要記得-1)，只是這次有說每個組合的每個值最多只能取一次，因此帶入遞回剩餘未取出的陣列元素不能包含自己的元素

func combine(sum int, nums int, target int, curComb []int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if sum == target && nums == 0 {
		...
	} else if sum < target {
		for i, v := range candidates {
			tmp = combine(sum+v, nums-1, target, append(curComb, v), candidates[i+1:])
			result = append(result, tmp...)
		}
	}
	return result
}

完整程式碼:

func combinationSum3(k int, n int) [][]int {
	candidates := make([]int, 9)
	for i := 1; i <= 9; i++ {
		candidates[i-1] = i
	}
	return combine(0, k, n, []int{}, candidates)
}
func combine(sum int, nums int, target int, curComb []int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if sum == target && nums == 0 {
		tmpCurComb := make([]int, len(curComb))
		copy(tmpCurComb, curComb)
		return [][]int{tmpCurComb}
	} else if sum < target {
		for i, v := range candidates {
			tmp = combine(sum+v, nums-1, target, append(curComb, v), candidates[i+1:])
			result = append(result, tmp...)
		}
	}
	return result
}

總結:

建議可以先參考先前Combination Sum的解法，解說較為詳細，基本上概念完全一樣，既然之前能找出數列中符合目標總合的所有組合，現在要找出特定長度的組合只要將其它的組合做篩選就沒有什麼大問題了。