77.combinations.md

77. Combinations

使用 Recursive 的方式來解:

1. 每次取一個數字加入 Combination
2. 只保留該數字之後的元素，與該 Combination 進入遞迴
   • 只保留之後的元素是為了避免重複的組合出現
3. 如果當前組合的長度已經等於 k，就加入 res 並返回

• Example for N = 4, K = 2

Solution:

var (
	res         = [][]int{}
	path        = []int{}
	length  int = 0
	maximum int = 0
)

func combine(n int, k int) [][]int {
	res, path = [][]int{}, []int{}
	length, maximum = k, n
	backtracking(1, 0)
	return res
}

func backtracking(start, depth int) {
	if depth >= length {
		res = append(res, append([]int{}, path...))
		return
	}
	for i := start; i <= maximum; i++ {
		path = append(path, i)
		backtracking(i+1, depth+1)
		path = path[:len(path)-1]
	}
}

Pruning Solution

這個題目可以 Pruning(剪枝)的原因是因為假如剩餘的數字已經不可能奏到 k 個，就可以提前返回， 這樣可以減少不必要的遞迴。

• Example for N = 4, K = 4

For pruning algorithm, please refer to reference

Pruning Solution:

var (
	res         = [][]int{}
	path        = []int{}
	length  int = 0
	maximum int = 0
)

func combine(n int, k int) [][]int {
	res, path = [][]int{}, []int{}
	length, maximum = k, n
	backtracking(1, 0)
	return res
}

func backtracking(start, depth int) {
	if depth >= length {
		res = append(res, append([]int{}, path...))
		return
	}
	for i := start; i <= maximum-(length-len(path))+1; i++ {
		path = append(path, i)
		backtracking(i+1, depth+1)
		path = path[:len(path)-1]
	}
}