Permutations 遞迴解法[leetcode]

題目會給你一個不重複的數列，請回傳全部可能的排列方式

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def callback(arr):
            if len(arr)==1:
                return [arr]
            
            #
            return_arr = []
            for idx in range(len(arr)):
                sub_arr = arr[:idx]+arr[idx+1:]
                exist = [arr[idx]]
                for result in callback(sub_arr):
                    return_arr.append(exist+result)

            return return_arr
        return callback(nums)

遞迴解法都會有兩個部分，一個是停止條件，另一個是遞減條件。

停止條件通常是程式執行到最小的時候，以這個例子來說就是，當參數陣列只有一個元素時，直接回傳。

if len(arr)==1:
    return [arr]

另一個是遞減條件，這邊的想法是：

1. 將所有的保留元素(陣列中的其中一個數值)依序列出
2. 列出剩下的待選元素(除了1.步驟中選到的數值以外全部數值)，繼續使用遞迴方法簡化後回傳。
3. 將保留元素與2.步驟的結果組合。

return_arr = []
for idx in range(len(arr)):
    sub_arr = arr[:idx]+arr[idx+1:]
    exist = [arr[idx]]
    for result in callback(sub_arr):
        return_arr.append(exist+result)

return return_arr

不喜歡使用遞迴的話，這邊有別的方式。