leetcode(力扣) 46. 全排列 (回溯) (遞歸中的值和引用傳遞的問題)

文章目錄

• ​​題目描述​​
• ​​思路分析​​
• ​​遞歸中值和引用傳遞的問題。​​
• ​​完整代碼​​

題目描述

給定一個不含重複數字的數組 nums ，傳回其 所有可能的全排列 。你可以 按任意順序 傳回答案。

示例 1：

輸入：nums = [1,2,3]

輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]

輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1]

輸出：[[1]]

思路分析

回溯找所有排列組合的可能。

在網上找了下面這個圖，我覺得很清晰。

首先确定終止條件，顯然，當我們排列組合的長度等于題目所給的長度的時候就結束，這也同時說明達到了葉子節點。

在這個過程我們需要記錄已經使用過的數字，目前的結果集，還有總的結果集。

來一下過程模拟:

• 周遊到1，檢視1是否使用過，看他是不是在used裡面，不在，則加入used，加入目前結果集合path，然後遞歸調用本函數。
• 又周遊1，看他是否在used裡面，顯然在，結束本次循環，去周遊第二個數 2。 2不在used裡面，是以加入used，加入目前結果集合path，然後遞歸調用本函數。
• 又周遊1，1在used裡，周遊2，2也在used裡，周遊3，3不在used裡，是以3加入used，加入path。此時顯然 path的長度已經等于題目所給的數組長度，則将此時path的答案加入最終答案集合，然後return函數， 開始回溯，将used回退，path回退，
• 這裡因為周遊的是3，是以回退之後，目前的 循環也完成了，是以回退過程是 [1,2,3]->[1,2]->[1]，顯然下一個周遊的數是3(剛才2已經周遊過了嘛)。這裡說的可能比較亂，調試一下程式看看過程就清楚了。

遞歸中值和引用傳遞的問題。

# 遞歸的時候變量都儲存在棧裡，result裡面存的是的位址。
      但是，當遞歸函數運作結束，就被pop掉了。
            # []是引用 傳址調用  引用傳遞 
            # [:] 是複制 傳值調用
            # 在這裡 直接append也是空資料 而extend卻可以
            # 說明append直接是傳位址引用，當遞歸回去的時候引用被釋放了，而extend是疊代值再添加屬于值的使用。
            # 是以 切片也是複制的值傳遞  類似于 deepcopy？？      

完整代碼

= []  # 中間結果集
        res = []  # 最終結果集
        temp = []  # 已經用過的數字記錄

        def backtrack(num, temp):
            if len(path) == len(num):
                # 目前的中間結果已經滿足條件 即長度一樣了
                res.append(path[:])
                # res.extend(path)
                # res.append(path)
                return

            for i in range(len(num)):
                if num[i] in temp:
                    continue  # 如果目前數字在中間結果集中 表明目前數字已經用過了
                path.append(num[i])  # 加入中間結果集
                temp.append(num[i])  # 加入已用過數字記錄集
                backtrack(num, temp)
                path.pop()
                temp.pop()

        backtrack(num, temp)
        return