1、 組合和子集問題

組合問題需要滿足一定要求才算作一個答案，比如數量要求（k個數），累加和要求（=target）。
子集問題是只要構成一個新的子集就算作一個答案。

進階：去重邏輯。

1. 一般都是要對同層去重。比如[1,1,2,2,2]
   放置第一個位置的數時，如果已經使用過第一個1了，那么他的所有組合和子集一定包含第二個1，所以去重邏輯就是同層不能出現相同的數。

• 對于一個順序數組，通常直接與前一個數比較即可。

for i in range(index+1, n):if i==index+1 or nums[i]!=nums[i-1]:dfs(i,[],target)

• 對于一個亂序數組，則需要用哈希表存儲同層出現過的數。

hash = set()
for i in range(index+1, n):if i==index+1 or (nums[i] not in hash):hash.add(nums[i])dfs(i, [])

2. 實際上上面的兩段代碼還蘊含了另一個去重，即不同層不能用同一個下標的數，所以這里索引時是從index+1開始。

2、分割問題

我們定義[start:end] **（左閉右閉）**這段區間為分割出來的子串，對他進行條件判斷。在python中對應的是s[start: end+1]，end指向某個字符后面，表示切割到這個字符。start則為上一步的end+1。可以看下面這幅圖，比較直觀。理解了怎么分割字符串，剩下的就套回溯的模板就可以了。

    def partition(self, s: str) -> List[List[str]]:n = len(s)res = []def ishuiwen(s):return s==s[::-1]def dfs(start,end,stack):ss = s[start:end+1]if not ishuiwen(ss):returnstack.append(ss)if end == n-1:res.append(stack.copy())return for i in range(end+1,n):dfs(end+1, i, stack.copy())for i in range(n):dfs(0, i, [])return res