树形递归--打印给定数字的子序列。

Question

问题说明。

// m is the number, n is upto-length of subsequences
// m = 20125, n =3  should print 201, 202, 205, 212, 215, 225, 012, 015, 125
// m = 20125, n =2 should print 20, 21, 22, 25, 01, 02, 05, 12, 15, 25
// m = 20125, n =1 should print 2, 0, 1, 2, 5
// m = 20125, n =4 should print 2012, 2015, 2125, 0125, 2025
// m = 20125, n =5 should print 20125

---

下面是用GoLang实现的递归解决方案。

package recursion

import (
    "fmt"
    "strconv"
)

// m is the number, n is upto-length of subsequences
// m = 20125, n =3  should print 201, 202, 205, 212, 215, 225, 012, 015, 125
// m = 20125, n =2 should print 20, 21, 22, 25, 01, 02, 05, 12, 15, 25
// m = 20125, n =1 should print 2, 0, 1, 2, 5
// m = 20125, n =4 should print 20125

func PrintSubSequence(m int, n int) {

    numDigits := digits(m)

    if n >= 1 && numDigits >= n { // m != 0
        for i := 1; i <= numDigits-n+1; i++ { // tree recurion
            firstInvocToIter := true
            var slice []string
            var findSubSequence func(int, int)

            findSubSequence = func(m int, n int) {

                if n == 1 { // base case
                    for m != 0 {
                        slice = append(slice, strconv.Itoa(m%10))
                        m = m / 10
                    }
                    return
                } else {
                    if firstInvocToIter {
                        firstInvocToIter = false
                        findSubSequence(m/tenToThePower(i), n-1)
                    } else {
                        findSubSequence(m/10, n-1)
                    }

                    for i, value := range slice {
                        slice[i] = value + strconv.Itoa(m%10)
                    }
                }

            }
            findSubSequence(m, n) // (20125, 3)
            fmt.Println(slice)
        }

    } else {
        return
    }

    PrintSubSequence(m/10, n)
}

func tenToThePower(times int) int {
    number := 1
    for times > 0 {
        number *= 10
        times--
    }
    return number
}

// Return the number of the digits of positive integer n
func digits(n int) int {
    if n <= 0 {
        return 0
    } else if n < 10 {
        return 1
    } else {
        allButLast, _ := split(n)
        return digits(allButLast) + 1
    }
}

---

package main

import (
    "github.com/myhub/cs61a/recursion"
)

func main() {

    recursion.PrintSubSequence(20125, 2) // prints duplicates as per debugging
    recursion.PrintSubSequence(20125, 3) // Works fine 
}

---

对于 recursion.PrintSubSequence(20125, 3) 输出就可以了。

[125 025 225]
[015 215]
[205]
[012 212]
[202]

对于 recursion.PrintSubSequence(20125, 2) 输出有重复()问题输出):

[25 15 05 25]        --> Valid
[15 05 25] --> duplicate
[05 25] --> duplicate
[25] --> duplicate
[12 02 22]           --> Valid
[02 22] --> duplicate
[22] --> duplicate
[01 21]              --> Valid
[21] --> duplicate
[20]                 --> Valid

---

这是否需要维护一组字符串？slice 一套

或

如何处理重复的内容？好像是 n==1 树型递归的基例给出了问题？

Answer 1

如果你把你的整数转换成字符串，那么它将更容易，我认为。

func PrintSubSequence(digits string, tmp string, idx int, sz int) {
    if len(tmp) == sz {  // if size reach then print
        fmt.Println(tmp)
        return
    }
    // here idx indicate in tmp string we already use till idx-1
    for i := idx; i < len(digits); i++ {
        tmp2 := tmp + string(digits[i]) // Add new digit in new variable to pass in recursion without change current tmp
        PrintSubSequence(digits, tmp2, i+1, sz)
    }
}
func main() {
    PrintSubSequence(strconv.Itoa(21025), "", 0, 2) // Convert interger into string
}

完整的代码在去游乐场 此处

Answer 2

这里是阿尔戈:-

1. 你需要从每个数字的角度来思考。所以，当你生成子序列时，要么一个数字可以是子序列的一部分，要么不能。
2. 当你考虑一个特定的数字时，递增一个计数器（例如，currentLength）.将到目前为止形成的序列添加到一个Set中，以避免重复。
3. 如果 currentLength 计数器已经达到了你给定的最大长度，那么停止当前子序列的形成。
4. 转入下一个序列的形成。