未分類

Combinations

Backtracking, Go, LeetCode

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example:

If n = 4 and k = 2, a solution is:

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

Default:

1
2
3
func combine(n int, k int) [][]int {
}

解答思路:

先前也有不少這種類似的題目，最主要是要用遞回的方式將現有的組合陣列與尚未被組合的陣列再次做組合，而且仔細觀查會發現為了要避免重覆的情況，每一次從尚未被組合的陣列取新的元素來跟現有陣列再次做組合時，該元素一定比現有陣列中的所有元素來的大，現有陣列的長度到達指定的長度才向上回傳存至結果之中，最後就是不斷透過遞回直到找出所有可能為止。

程式碼解說:

因為是要將1~n做排序組合，所以一開始就需要先準備儲有1~n的陣列，接著才將其帶入遞回中，其中第一個參數為現有的組合陣列，第二個則是要到達指定的長度數，最後一個則是尚未被組合的陣列

1
2
3
4
5
6
7
func combine(n int, k int) [][]int {
	candidates := make([]int, n)
	for i := 1; i <= n; i++ {
		candidates[i-1] = i
	}
	return recursive([]int{}, k, candidates)
}

接下來就是處理遞回之中的組合，如果現有陣列的長度到達指定的長度就向上回傳，注意在golang中不能直接回傳[][]int{curComb}，而是要再複製到空的陣列之中才做回傳，原因和slice特性有關，詳情可以到這邊看Go Slices，至於如果現有的陣列長度尚未到達直定長度，就從尚未被組合的陣列取新的元素來跟現有陣列做組合並再次放入遞回之中，而新的待組合陣列則是帶入自身之後的所有元素以避免之後的組合出現重覆，最後將每次得到的回傳放入結果之中，待找出所有組合最後才向上回傳現有的結果組合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 {
		tmp = recursive(append(curComb, v), k, 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
func combine(n int, k int) [][]int {
	candidates := make([]int, n)
	for i := 1; i <= n; i++ {
		candidates[i-1] = i
	}
	return recursive([]int{}, k, candidates)
}
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 {
		tmp = recursive(append(curComb, v), k, candidates[i+1:])
		result = append(result, tmp...)
	}
	return result
}

總結:

數序1~n要找出長度為k的所有組合，最主要是要用遞回的方式將現有的組合陣列與尚未被組合的陣列再次做組合，為了要避免重覆的情況，每一次從尚未被組合的陣列取新的元素來跟現有陣列再次做組合時，該元素一定要比現有陣列中的所有元素來的大，最後就是不斷透過遞回直到找出所有符合長度陣列的組合為止。

分享到