題目：

給定一個字符串S,請將S分割成一些子串，使每個子串都是回文串，返回S所有可能的分割方案

---

方法一：回溯+深度優先搜索

1. 主要思想

• 使用 深度優先搜索（DFS） 遍歷 s 的所有可能劃分方式。
• 使用 回溯（Backtracking）嘗試所有可能的子串分割，并在搜索失敗時撤銷上一步決策。
• 剪枝優化：如果某個子串不是回文，就直接跳過，減少不必要的遞歸調用。

以 "aab" 為例，我們一步步拆解執行過程：

(1) 遞歸函數 dfs(i)

• dfs(i) 代表從索引 i 開始嘗試分割 s[i:]。
• 終止條件：當 i == n（遍歷完整個字符串），說明找到了一個完整的回文劃分，將 path 復制到 ans 中。

(2) 遍歷所有可能的子串

• 設 j 為子串 s[i:j+1] 的結束索引：
  • 如果 s[i:j+1] 是回文，則遞歸處理 s[j+1:]。
  • 如果 s[i:j+1] 不是回文，就跳過這個分割。

Step 1: dfs(0)

• i = 0，遍歷 j 從 0 到 2：
  1. s[0:1] = "a" 是回文 → 加入 path → dfs(1)
  2. s[0:2] = "aa" 是回文 → 加入 path → dfs(2)
  3. s[0:3] = "aab" 不是回文 → 跳過

Step 2: dfs(1)（繼續從 "a" 后開始）

• i = 1，遍歷 j 從 1 到 2：
  1. s[1:2] = "a" 是回文 → 加入 path → dfs(2)

Step 3: dfs(2)（繼續從 "a" 后開始）

• i = 2，遍歷 j 從 2 到 2：
  1. s[2:3] = "b" 是回文 → 加入 path → dfs(3)

Step 4: dfs(3)（終止條件）

• i = 3 == len(s)，找到一個完整的劃分 ["a", "a", "b"]，存入 ans，然后回溯。

---

4. 回溯過程

• 回溯到 dfs(2)，撤銷 "b"，繼續找其他可能（沒有）。
• 回溯到 dfs(1)，撤銷 "a"，嘗試 "aa"：
  • "aa" 是回文 → dfs(2)
  • 繼續拆分 s[2:3] = "b"，得到 ["aa", "b"]，存入 ans。

最終 ans = [["a", "a", "b"], ["aa", "b"]]。

class Solution(object):def partition(self, s):""":type s: str:rtype: List[List[str]]"""n=len(s)  #字符串的長度ans=[]   #存儲所有符合條件的回文子串分割方案path=[]  #存儲當前的分割方案，DFS過程中會不斷更新def dfs(i):if i==n:  #被分割完畢ans.append(path[:])  #復制return for j in range(i,n):t=s[i:j+1]  #t是s的子串，索引 i 到 jif t==t[::-1]:  #生成t的逆序，判斷是否為回文path.append(t)#將 t 加入當前分割方案dfs(j+1)# 遞歸處理s[j+1:]path.pop() #回溯dfs(0)return ans

時間復雜度：O(n2n)，其中?n?為?s?的長度

空間復雜度：O(n)