思路：這是經(jīng)典的回溯問題，構(gòu)造一個回溯函數(shù)，參數(shù)為first（指示first左邊的數(shù)都是排列好的），然后不斷用first右邊的數(shù)放在first位置上測試是否可行。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # 所有數(shù)都填完了
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 動態(tài)維護數(shù)組
                nums[first], nums[i] = nums[i], nums[first]
                # 繼續(xù)遞歸填下一個數(shù)
                backtrack(first + 1)
                # 撤銷操作
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2

思路：今天的兩題都是回溯法的題目，子集處理步驟和全排列的很像。首先有一個循環(huán)，用來控制生成長度不同的子集。每一個元素都有放進去和不放進去兩種情況，放進去后還有撤銷的操作，使之能恢復(fù)到最初的狀態(tài)。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first = 0, curr = []):
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
            for i in range(first, n):
                # add nums[i] into the current combination
                curr.append(nums[i])
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack
                curr.pop()
        
        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output