---

一、78. 子集

中等
給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

示例 1：
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
輸入：nums = [0]
輸出：[[],[0]]

1、nums = [1,2,3]為例把求子集抽象為樹型結構

從圖中紅線部分，可以看出遍歷這個樹的時候，把所有節點都記錄下來，就是要求的子集集合。

如果把 子集問題、組合問題、分割問題都抽象為一棵樹的話，那么組合問題和分割問題都是收集樹的葉子節點，而子集問題是找樹的所有節點！
其實子集也是一種組合問題，因為它的集合是無序的，子集{1,2} 和 子集{2,1}是一樣的。
那么既然是無序，取過的元素不會重復取，寫回溯算法的時候，for就要從startIndex開始，而不是從0開始！

2、回溯三部曲

1、遞歸函數參數
全局變量數組path為子集收集元素，二維數組result存放子集組合。（也可以放到遞歸函數參數里）
遞歸函數參數在上面講到了，需要startIndex。

剩余集合為空的時候，就是葉子節點。
那么什么時候剩余集合為空呢？
就是startIndex已經大于數組的長度了，就終止了，因為沒有元素可取了，代碼如下:

class S79:def func(self,nums):result=[]def dfs(path,startIndex):result.append(path[:])  #todo 收集結果代碼為什么放到這里？因為每進入一層遞歸需要把當前結果放入resultif startIndex>=len(nums):returnfor i in range(startIndex,len(nums)):path.append(nums[i])dfs(path,i+1)       #todo i+1：保證之前傳入的數，不再重復使用path.pop()dfs([],0)return resultr=S79()
nums=[1,2,3]
print(r.func(nums))

二、90. 子集 II

中等
給你一個整數數組 nums ，其中可能包含重復元素，請你返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。返回的解集中，子集可以按 任意順序 排列。

示例 1：
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
輸入：nums = [0]
輸出：[[],[0]]

1、本題搜索的過程抽象成樹形結構如下：

從圖中可以看出，同一樹層上重復取2 就要過濾掉，同一樹枝上就可以重復取2，因為同一樹枝上元素的集合才是唯一子集！

startIndex的目的是不再取當前數之前的數，防止重復 [2,1]——》[1,2]重復了

class S90:def func(self,nums):result=[]def dfs(path,used,startIndex):result.append(path[:])if len(nums)==len(path):returnfor i in range(startIndex,len(nums)):if i>0 and nums[i]==nums[i-1] and used[i-1]==False:continueif used[i]==True:continueused[i]=Truepath.append(nums[i])dfs(path,used,i+1)used[i]=Falsepath.pop()dfs([],[False]*len(nums),0)return resultr=S90()
nums=[1,2,2]
print(r.func(nums))

三、39. 組合總和

中等
給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。
candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。
對于給定的輸入，保證和為 target 的不同組合數少于 150 個。

示例 1：
輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

示例 2：
輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
輸入: candidates = [2], target = 1
輸出: []

1、回溯三部曲

1、遞歸函數參數
這里依然是定義兩個全局變量，二維數組result存放結果集，數組path存放符合條件的結果。（這兩個變量可以作為函數參數傳入）

首先是題目中給出的參數，集合candidates, 和目標值target。

此外我還定義了int型的sum變量來統計單一結果path里的總和，其實這個sum也可以不用，用target做相應的減法就可以了，最后如何target==0就說明找到符合的結果了，但為了代碼邏輯清晰，我依然用了sum。

本題還需要startIndex來控制for循環的起始位置，對于組合問題，什么時候需要startIndex呢？
我舉過例子，如果是一個集合來求組合的話，就需要startIndex；
如果是多個集合取組合，各個集合之間相互不影響，那么就不用startIndex

2、遞歸終止條件
在如下樹形結構中：

從葉子節點可以清晰看到，終止只有兩種情況，sum大于target和sum等于target。
sum等于target的時候，需要收集結果，代碼如下：

if total > target:return
if total == target:result.append(path[:])return

3、單層搜索的邏輯

單層for循環依然是從startIndex開始，搜索candidates集合。
本題元素為可重復選取的。
如何重復選取呢，代碼注釋

for i in range(startIndex, len(candidates)):total += candidates[i]path.append(candidates[i])dfs(total, i, path)		# 不用i+1了，表示可以重復讀取當前的數total -= candidates[i]path.pop()

總代碼：

class S39:def func(self, candidates, target):result = []def dfs(total, startIndex, path):if total > target:returnif total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):total += candidates[i]path.append(candidates[i])dfs(total, i, path)total -= candidates[i]path.pop()dfs(0, 0, [])return resultr = S39()
candidates = [2,3,6,7]
target = 7
print(r.func(candidates, target))

2、剪枝優化

以及上面的版本一的代碼大家可以看到，對于sum已經大于target的情況，其實是依然進入了下一層遞歸，只是下一層遞歸結束判斷的時候，會判斷sum > target的話就返回。

其實如果已經知道下一層的sum會大于target，就沒有必要進入下一層遞歸了。
那么可以在for循環的搜索范圍上做做文章了。
對總集合排序之后，如果下一層的sum（就是本層的 sum + candidates[i]）已經大于target，就可以結束本輪for循環的遍歷。

for循環剪枝代碼如下：

for i in range(startIndex, len(candidates)):if total+candidates[i]>target:continuetotal += candidates[i]path.append(candidates[i])dfs(total, i, path)total -= candidates[i]path.pop()

總代碼

class S39:def func(self, candidates, target):result = []def dfs(total, startIndex, path):# if total > target:#     returnif total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total+candidates[i]>target:continuetotal += candidates[i]path.append(candidates[i])dfs(total, i, path)total -= candidates[i]path.pop()dfs(0, 0, [])return resultr = S39()
candidates = [2,3,6,7]
target = 7
print(r.func(candidates, target))

四、LCR 082. 組合總和 II

中等
給定一個可能有重復數字的整數數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。
candidates 中的每個數字在每個組合中只能使用一次，解集不能包含重復的組合。

示例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:
輸入: candidates = [2,5,2,1,2], target = 5,
輸出:
[
[1,2,2],
[5]
]

1、思路

這道題目和39.組合總和如下區別：
本題candidates 中的每個數字在每個組合中只能使用一次。
本題數組candidates的元素是有重復的，而39.組合總和是無重復元素的數組candidates
最后本題和39.組合總和要求一樣，解集不能包含重復的組合。

本題的難點在于區別2中：集合（數組candidates）有重復元素，但還不能有重復的組合。

2、樹形結構如圖所示：

3、回溯三部曲

a、遞歸函數參數
與39.組合總和套路相同，此題還需要加一個bool型數組used，用來記錄同一樹枝上的元素是否使用過。
這個集合去重的重任就是used來完成的。
b、遞歸終止條件
與39.組合總和相同，終止條件為 sum > target 和 sum == target。。
c、單層搜索的邏輯
這里與39.組合總和最大的不同就是要去重了。

前面我們提到：要去重的是“同一樹層上的使用過”，如何判斷同一樹層上元素（相同的元素）是否使用過了呢。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就說明：前一個樹枝，使用了candidates[i - 1]，也就是說同一樹層使用過candidates[i - 1]。
此時for循環里就應該做continue的操作。

我在圖中將used的變化用橘黃色標注上，可以看出在candidates[i] == candidates[i - 1]相同的情況下：

used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過
used[i - 1] == false，說明同一樹層candidates[i - 1]使用過

可能有的錄友想，為什么 used[i - 1] == false 就是同一樹層呢，因為同一樹層，used[i - 1] == false 才能表示，當前取的 candidates[i] 是從 candidates[i - 1] 回溯而來的。

而 used[i - 1] == true，說明是進入下一層遞歸，去下一個數，所以是樹枝上，如圖所示：

class LCR082:def func(self, candidates, target):candidates.sort()result = []def dfs(total, path, used, startIndex):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:continueif i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == False:continueif used[i] == True:continueused[i] = Truetotal += candidates[i]path.append(candidates[i])dfs(total, path, used, i + 1)total -= candidates[i]path.pop()used[i]=Falsedfs(0, [], [False] * len(candidates), 0)return resultr = LCR082()
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
print(r.func(candidates, target))

---