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

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 recursionimport (    "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 20125func 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) {

    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. 移动到下一个序列形成。