46. 全排列
給定一個不含重復數(shù)字的數(shù)組 nums 思杯，返回其 所有可能的全排列 挎狸。你可以 按任意順序 返回答案武花。
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracing(nums):
# 終止條件：當路徑上的元素數(shù)量等于最大值
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if nums[i] not in path:
path.append(nums[i])
# 遞歸搜索
backtracing(nums)
# 撤銷選擇
path.pop()
backtracing(nums)
return res
47. 全排列 II
給定一個可包含重復數(shù)字的序列 nums 修赞，按任意順序 返回所有不重復的全排列询件。
輸入：nums = [1,1,2]
輸出：
[[1,1,2],
[1,2,1],
[2,1,1]]
# 對于數(shù)組中包含重復數(shù)字杆融，需要對重復的數(shù)字提前進行標注楞卡，在訪問時及時去重
class Solution:
res = []
path = []
# 回溯算法
def backtracing(self, nums: List[int], visited: List[bool]):
# 遞歸的終止條件
if len(nums) == len(self.path):
self.res.append(self.path[:])
return
for i in range(len(nums)):
# 需要及時去重，如果相同元素之前訪問過，則跳過
if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
continue
# 元素沒有訪問過
if not visited[i]:
# 訪問之后需要進行標記
visited[i] = True
self.path.append(nums[i])
self.backtracing(nums, visited)
self.path.pop()
# 回溯之后對元素進行恢復
visited[i] = False
# 主函數(shù)
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 清除緩存
self.res.clear()
self.path.clear()
# 需要對nums進行排序
nums.sort()
# 用于記錄是否訪問過相同元素
visited = [False]*len(nums)
self.backtracing(nums, visited)
return self.res
90. 子集 II
給你一個整數(shù)數(shù)組 nums 蒋腮，其中可能包含重復元素淘捡，請你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復的子集池摧。返回的解集中案淋，子集可以按 任意順序 排列。
示例 1：
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution:
def backtrace(self, nums, index, res, path):
# 空數(shù)組
res.append(path[:])
# 從第0個位置開始险绘，進行深度優(yōu)先搜索
for i in range(index, len(nums)):
if i > index and nums[i] == nums[i-1]:
continue
path.append(nums[i])
self.backtrace(nums, i+1, res, path)
path.pop()
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
# 首先對數(shù)組排序
nums.sort()
res, path = [], []
self.backtrace(nums, 0, res, path)
return res
784. 字母大小寫全排列
給定一個字符串 s 踢京，通過將字符串 s 中的每個字母轉變大小寫，我們可以獲得一個新的字符串宦棺。
返回 所有可能得到的字符串集合 瓣距。以 任意順序 返回輸出。
輸入：s = "a1b2"
輸出：["a1b2", "a1B2", "A1b2", "A1B2"]
# 大小寫轉換
class Solution:
def dfs(self, s, i, path, ans):
# 終止條件
if i == len(s):
ans.append(path[:])
return
self.dfs(s, i+1, path+s[i], ans)
# 當字符為小寫字母代咸，轉換為大寫并添加
if ord('a') <= ord(s[i]) <= ord('z'):
self.dfs(s, i+1, path + s[i].upper(), ans)
# 當字符為大寫字母是蹈丸，轉換為小寫并添加
elif ord('A') <= ord(s[i]) <= ord('Z'):
self.dfs(s, i+1, path + s[i].lower(), ans)
def letterCasePermutation(self, s: str) -> List[str]:
ans, path = [], ''
self.dfs(s, 0, path, ans)
return ans
39. 組合總和
給你一個 無重復元素 的整數(shù)數(shù)組 candidates 和一個目標整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標數(shù) target 的 所有 不同組合 呐芥，并以列表形式返回逻杖。你可以按 任意順序 返回這些組合。
candidates 中的 同一個 數(shù)字可以 無限制重復被選取 思瘟。如果至少一個數(shù)字的被選數(shù)量不同荸百，則兩種組合是不同的。
對于給定的輸入滨攻，保證和為 target 的不同組合數(shù)少于 150 個够话。
輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 光绕。注意 2 可以使用多次女嘲。
7 也是一個候選， 7 = 7 诞帐。
僅有這兩種組合欣尼。
class Solution:
path = []
res = []
def backtracing(self, candidates: List[int], target:int, sum_all:int, start_index:int):
# 遞歸的終止條件
if sum_all > target:
return
if sum_all == target:
self.res.append(self.path[:])
return
# 開始遍歷查找
for i in range(start_index, len(candidates)):
# 循環(huán)終止條件
if sum_all + candidates[i] > target:
break
sum_all += candidates[i]
self.path.append(candidates[i])
# 回溯
self.backtracing(candidates, target, sum_all, i)
sum_all -= candidates[i]
self.path.pop()
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.path.clear()
self.res.clear()
candidates.sort()
self.backtracing(candidates, target, 0, 0)
# print(self.res)
return self.res
40. 組合總和 II
給定一個候選人編號的集合 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合停蕉。
candidates 中的每個數(shù)字在每個組合中只能使用 一次 愕鼓。
注意：解集不能包含重復的組合。
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
# 本題主要考慮去重
class Solution:
res = []
path = []
def backtracing(self, candidates: List[int], target: int, sum_all: int, start_index: int):
# 遞歸的終止條件
if sum_all > target:
return
if sum_all == target:
self.res.append(self.path[:])
return
# 進行回溯
for i in range(start_index, len(candidates)):
# 終止條件
if sum_all + candidates[i] > target:
break
# 去重操作
if i > start_index and candidates[i] == candidates[i-1]:
continue
sum_all += candidates[i]
self.path.append(candidates[i])
self.backtracing(candidates, target, sum_all, i+1)
sum_all -= candidates[i]
self.path.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.res.clear()
self.path.clear()
# 先進行排序
candidates.sort()
self.backtracing(candidates, target, 0, 0)
return self.res
