藍橋杯湊平方數（dfs-組合）

1. 問題描述：

把0~9這10個數字，分成多個組，每個組恰好是一個平方數，這是能夠辦到的。 比如：0, 36, 5948721 

再比如： 

1098524736 

1, 25, 6390784 

0, 4, 289, 15376等等... 

注意，0可以作為獨立的數字，但不能作為多位數字的開始。 分組時，必須用完所有的數字，不能重複，不能遺漏。 如果不計較小組内資料的先後順序，請問有多少種不同的分組方案？ 

輸出

輸出一個整數表示答案 

來源：http://oj.ecustacm.cn/problem.php?id=1307

2. 思路分析：

① 一開始想到的是生成0~9這十個數字的全排列然後對每一個生成的排列進行切分看是否使得每一組都是一個平方數，這裡存在一個很麻煩的操作是處理數字0的操作，因為題目要求數字0是不可以作為多位數字的開始，是以這是一個需要處理的細節，而且對每一個生成的排列都是這樣分割導緻計算耗時很大，并且題目要求是不計較小組内資料的先後順序，而全排列是對于不同順序的排列都是算做兩種的又是一個需要處理的細節，是以整體感覺還是很難處理，後面想到另外一個解決的辦法：因為每一個數字都是平方數字而且最大的數字是987654321，是以我們可以生成這個範圍内的所有的平方數，這樣可以避免數字0作為多位數字開始的問題。并且在生成平方數字的時候需要判斷目前的數字中的位是否存在重複的數字，如果出現了重複的數字那麼這個平方數是不符合題目要求的，我們在生成平方數字的時候可以使用一個方法isOne來判斷是否目前數字各個位的數字是否存在重複，具體的操作是：将目前的平方數字轉為字元串，并且将字元串加入到set集合中判斷set集合的長度是否與原來字元串的長度想到，如果相等說明不存在重複的元素，目前的平方數字是符合題目要求的。

② 在①步中我們可以将[0, 9876543210]範圍的平方數字存儲到一個一維清單nums中，因為是不計較小組内資料的先後順序是以目前這道題目是一個組合問題，其實表達的意思是目前我有這麼多個數字存儲在nums中（實際上存儲的是平方數字的字元串形式這樣好計算序列長度），需要做的是在nums中的這些數字中選擇出x個數字使得選出x個數字的長度滿足10（這個長度是經過set集合之後的長度：需要滿足題目中0-9的數字隻能出現一次的條件）。計算組合方案可以通過遞歸解決，通過for循環中遞歸選擇出x個數字。使用遞歸計算組合數目也是固定的套路，在遞歸的方法傳遞目前遞歸的位置，在for循環中遞歸表示的是可以選擇目前的位置的元素也可以不選擇目前的元素，當周遊到目前的位置的時候表示選擇目前這個位置的元素，當傳回到這一層進入for循環的下一個元素的時候表示不選擇這個元素，我在之前也寫過一篇生成組合方案的例子。下面表示的是for循環中遞歸的過程，主要是for循環遞歸的範圍與下一次遞歸的位置

③ 我們在往下遞歸之前需要進行減枝（下圖中的if判斷與return語句都屬于減枝），沒有經過減枝遞歸下去計算最終的結果會有點久。經過下面的減枝之後明顯很快就計算出結果。先判斷之前已經生成序列的長度加上目前的遞歸位置對應的平方數字的長度是否小于等于10，如果滿足才遞歸下去，如果發現大于10這個時候一個比較好的減枝方法是直接return到上一層，而不是continue（這樣可以避免for循環中嘗試目前位置後面的平方數字），因為我們知道目前位置i的平方數字的長度加上原來序列的長度已經超出了10那麼i位置後面的數字更加不用嘗試了(平方數字在生成的時候都是從小到大的順序的)，傳回到上一層嘗試其他的數字即可。通過這個減枝那麼計算結果就很快了，是以有的時候在遞歸的時候需要多想想怎麼樣減枝才能夠避免計算哪些沒有用的遞歸方案

④ 在遞歸方法中可以傳遞一個清單來記錄中間遞歸生成的結果這樣當到達了遞歸出口之後可以輸出清單中記錄的結果驗證是否正确。而且我們還可以将結果通過輸出語句記錄到檔案中更友善檢視，最終的答案是300。其實這道題目的本質是計算組合的數目，根據遞歸計算組合方案的套路即可，其中需要根據題目的要求注意細節，能夠減枝就盡量減枝，減少耗時。

3. 代碼如下：

from typing import List
res = 0


# 判斷目前的平方數字中的位是否存在重複
def isOne(n: int):
    s = str(n)
    return len(set(s)) == len(s)

# index表示目前遞歸的位置, curlen表示目前的序列長度, rec記錄生成的序列結果
def dfs(nums: List[str], index: int, curlen: int, rec: List[str]):
    global res, file
    if curlen == 10:
        # 如果生成的序列沒有重複的數字說明滿足條件
        if len(set("".join(rec))) == 10:
            print(rec)
            res += 1
    for i in range(index, len(nums)):
        # 目前序列長度+目前的平方數字的長度小于等于10才遞歸否則return到上一層
        if curlen + len(nums[i]) <= 10:
            rec.append(nums[i])
            dfs(nums, i + 1, curlen + len(nums[i]), rec)
            # 回溯
            rec.pop()
        else: return


if __name__ == '__main__':
    i = 0
    nums = list()
    # 生成平方數字的位沒有重複的數字添加到清單中(轉為字元串後面計算組合數的時候會比較好計算序列長度)
    while i * i < 9876543210:
        n = str(i * i)
        if isOne(n):
            nums.append(n)
        i += 1
    rec = list()
    dfs(nums, 0, 0, rec)
    print(res)
           

将結果通過print語句輸出到檔案中友善檢視：

from typing import List
res = 0
file = open("data.txt", "w")


# 判斷目前的平方數字中的位是否存在重複的數字
def isOne(n: int):
    s = str(n)
    return len(set(s)) == len(s)


def dfs(nums: List[str], index: int, curlen: int, rec: List[str]):
    global res, file
    if curlen == 10:
        if len(set("".join(rec))) == 10:
            print(rec, file=file)
            res += 1
    for i in range(index, len(nums)):
        if curlen + len(nums[i]) <= 10:
            rec.append(nums[i])
            dfs(nums, i + 1, curlen + len(nums[i]), rec)
            rec.pop()
        else: return


if __name__ == '__main__':
    # 思路是先生成這些平方數字然後在平方數字選出若幹個數字
    i = 0
    nums = list()
    while i * i < 9876543210:
        n = str(i * i)
        if isOne(n):
            nums.append(n)
        i += 1
    rec = list()
    dfs(nums, 0, 0, rec)
    print(res)