01234可以組成多少個不重復的三位數(shù)(0123能組成幾個不重復三位數(shù))

來源：好上學 ??時間：2022-09-06

遞歸套娃

前言

今天看到一個超級簡單的算法題，但是我當時思路往遞歸，逐級篩選里面想了。結(jié)果百度查查答案，超級簡單。
真是慚愧慚愧，不過我還是堅持用遞歸實現(xiàn)了，因為用遞歸的方案，可以適用于任何給定數(shù)據(jù)和指定位數(shù)。

傳統(tǒng)解法

如下所示，因為題目是找1、2、3、4組合的三位數(shù)，因此可以用三重循環(huán)，遍歷所有組合，篩選不重復組合即可。
但是該方案，如果給定數(shù)據(jù)改變，組合位數(shù)改變，那代碼就得大改，所以不是一個通用的好方法。

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}遞歸求解

下面方案是通過遞歸，依次為某一位分配數(shù)字，并將剩余組合依次賦值下一位。
該方法只需要改變data數(shù)據(jù)，以及numLen的指定位數(shù)就可以靈活地計算所有組合。

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 }}完整代碼

執(zhí)行結(jié)果如下，兩種方案結(jié)果完全一致：

[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 }}總結(jié)