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

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)

}

这是否需要维护一组字符串？包含slice在一个集合中

或者

如何处理重复？看起来n==1树递归的基本情况有问题？

Answer 1

如果您将整数转换为字符串，那么我认为会更容易。func PrintSubSequence(digits string, tmp string, idx int, sz int) {&nbsp; &nbsp; if len(tmp) == sz {&nbsp; // if size reach then print&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(tmp)&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; }&nbsp; &nbsp; // here idx indicate in tmp string we already use till idx-1&nbsp; &nbsp; for i := idx; i < len(digits); i++ {&nbsp; &nbsp; &nbsp; &nbsp; tmp2 := tmp + string(digits[i]) // Add new digit in new variable to pass in recursion without change current tmp&nbsp; &nbsp; &nbsp; &nbsp; PrintSubSequence(digits, tmp2, i+1, sz)&nbsp; &nbsp; }}func main() {&nbsp; &nbsp; PrintSubSequence(strconv.Itoa(21025), "", 0, 2) // Convert interger into string}

Answer 2

算法在这里： -您需要从每个数字的角度进行思考。因此，当您生成子序列时，一个数字可以是子序列的一部分，也可以不是。当你考虑一个特定的数字时，增加一个计数器（比如 currentLength）。将到目前为止形成的序列添加到 Set 以避免重复。如果 currentLength 计数器已达到您给定的最大长度，则停止当前子序列的形成。移动到下一个序列形成。