有1、2、3、4個數字，能組成多少個互不相同 且無重複數字的三位數？都是多少？
前言
今天看到一個超級簡單的演算法題，但是我當時思路往遞歸，逐級篩選裡面想了。結果百度查查答案，超級簡單。
真是慚愧慚愧，不過我還是堅持用遞歸實現了，因為用遞歸的方案，可以適用於任何給定數據和指定位數。
傳統解法
如下所示，因為題目是找1、2、3、4組合的三位數，因此可以用三重循環，遍歷所有組合，篩選不重複組合即可。
但是該方案，如果給定數據改變，組合位數改變，那程式碼就得大改，所以不是一個通用的好方法。
func useNormal() []int {
var ret []int
for i := 1; i < 5; i++ {
for j := 1; j < 5; j++ {
for k := 1; k < 5; k++ {
if i != j && j != k && i != k {
ret = append(ret, i*100+j*10+k)
}
}
}
}
return ret
}
遞歸求解
下面方案是通過遞歸，依次為某一位分配數字，並將剩餘組合依次賦值下一位。
該方法只需要改變data數據，以及numLen的指定位數就可以靈活地計算所有組合。
func useRecursion() []int {
var (
data = []int{1, 2, 3, 4}
numLen = 3
tmp = make([]int, numLen)
ret []int
)
findNum(data, tmp, numLen, &ret)
return ret
}
func findNum(data, tmp []int, dep int, ret *[]int) {
for i, v := range data {
if dep--; dep < 0 {
sum := 0
for i := len(tmp) - 1; i >= 0; i-- {
sum = sum*10 + tmp[i]
}
*ret = append(*ret, sum)
return
}
tmp[dep] = v // 當前選擇賦值
next := make([]int, 0, len(data))
next = append(next, data[:i]...)
next = append(next, data[i+1:]...)
findNum(next, tmp, dep, ret) // 剔除當前元素,進入下一級篩選
dep++
}
}
完整程式碼
執行結果如下，兩種方案結果完全一致：
[123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432] 24
[123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432] 24
package main
import "fmt"
func main() {
ret0 := useNormal()
fmt.Println(ret0, len(ret0))
ret1 := useRecursion()
fmt.Println(ret1, len(ret1))
}
func useNormal() []int {
var ret []int
for i := 1; i < 5; i++ {
for j := 1; j < 5; j++ {
for k := 1; k < 5; k++ {
if i != j && j != k && i != k {
ret = append(ret, i*100+j*10+k)
}
}
}
}
return ret
}
func useRecursion() []int {
var (
data = []int{1, 2, 3, 4}
numLen = 3
tmp = make([]int, numLen)
ret []int
)
findNum(data, tmp, numLen, &ret)
return ret
}
func findNum(data, tmp []int, dep int, ret *[]int) {
for i, v := range data {
if dep--; dep < 0 {
sum := 0
for i := len(tmp) - 1; i >= 0; i-- {
sum = sum*10 + tmp[i]
}
*ret = append(*ret, sum)
return
}
tmp[dep] = v // 當前選擇賦值
next := make([]int, 0, len(data))
next = append(next, data[:i]...)
next = append(next, data[i+1:]...)
findNum(next, tmp, dep, ret) // 剔除當前元素,進入下一級篩選
dep++
}
}
總結
凡事有簡單方案，也有複雜方案，簡單往往不能通用，多想想通用方案，嘗試解決一類問題而不是某一個問題。
