思路：這是經(jīng)典的回溯問(wèn)題，構(gòu)造一個(gè)回溯函數(shù)，參數(shù)為first（指示first左邊的數(shù)都是排列好的）监嗜，然后不斷用first右邊的數(shù)放在first位置上測(cè)試是否可行。
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):
# 動(dòng)態(tài)維護(hù)數(shù)組
nums[first], nums[i] = nums[i], nums[first]
# 繼續(xù)遞歸填下一個(gè)數(shù)
backtrack(first + 1)
# 撤銷(xiāo)操作
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/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有抡谐。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)裁奇，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
2
![]()
思路：今天的兩題都是回溯法的題目麦撵，子集處理步驟和全排列的很像刽肠。首先有一個(gè)循環(huán)，用來(lái)控制生成長(zhǎng)度不同的子集免胃。每一個(gè)元素都有放進(jìn)去和不放進(jìn)去兩種情況音五，放進(jìn)去后還有撤銷(xiāo)的操作，使之能恢復(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
