3.1 索引常見面試題

索引的分類

• 什么是索引？

  索引是一種數(shù)據(jù)結構，可以幫助MySQL快速定位到表中的數(shù)據(jù)。使用索引，可以大大提高查詢的性能。

• 按「數(shù)據(jù)結構」分類：B+tree索引、Hash索引、Full-text索引。

  InnoDB 存儲引擎創(chuàng)建的聚簇索引或者二級索引默認使用的都是 B+Tree 這種數(shù)據(jù)結構。

• 按「存儲類型」分類：聚簇索引（主鍵索引）、二級索引（輔助索引）。術語“聚簇”表示數(shù)據(jù)行和相鄰的鍵值聚簇地存儲在一起。這也形象地說明了聚簇索引葉子節(jié)點的特點，保存表的完整數(shù)據(jù)。

  對于B + 樹來說，每個節(jié)點都是一個數(shù)據(jù)頁。B + 樹只有葉子節(jié)點才會存放數(shù)據(jù)，非葉子節(jié)點僅用來存放目錄項作為索引。所有節(jié)點按照索引鍵大小排序，構成雙向鏈表，便于順序查找和范圍查找。

  而B + Tree索引又可以分成聚簇索引和二級索引（非聚簇索引），它們區(qū)別就在于葉子節(jié)點存放的是什么數(shù)據(jù)。

  • 聚簇索引的葉子節(jié)點存放的是實際數(shù)據(jù)，所有完整的用戶記錄都存放在葉子節(jié)點。

    • InnoDB存儲引擎一定會為表創(chuàng)建一個聚簇索引，一般情況下會使用主鍵作為聚簇索引，且一張表只允許存在一個聚簇索引。

      • 如果沒有主鍵，就選擇第一個不包含 NULL 值的唯一列作為聚簇索引的索引鍵；

      • 在上面兩個都沒有的情況下，InnoDB 將自動生成一個隱式自增 id 列作為聚簇索引的索引鍵；

  • 由于一張表只能有一個聚簇索引，為了實現(xiàn)非主鍵字段的快速搜索，就引出了二級索引（非聚簇索引/輔助索引），它也是利用了 B+ 樹的數(shù)據(jù)結構，但是二級索引的葉子節(jié)點存放的是主鍵值，不是實際數(shù)據(jù)。

    • 回表，就是先檢索二級索引，找到葉子節(jié)點并獲取主鍵值，通過聚簇索引查詢到對應的葉子節(jié)點，也就是要查兩個 B+Tree 才能查到數(shù)據(jù)。

    • 索引覆蓋，就是當查詢的數(shù)據(jù)是主鍵值時，那么在二級索引就能查詢到，不用再去聚簇索引查，就表示發(fā)生了索引覆蓋，也就是只需要查一個 B+Tree就能找到數(shù)據(jù)。

• 按「字段特性」分類：主鍵索引、唯一索引、普通索引、前綴索引。

  • 主鍵索引也叫聚簇索引，就是建立在主鍵字段上的索引，在創(chuàng)建表的時候一起創(chuàng)建，一張表最多只有一個主鍵索引，索引列的值不允許有空值。
  • 唯一索引建立在 UNIQUE 字段上的索引，表示索引列的值必須唯一，允許有空值。一張表可以有多個唯一索引。
  • 普通索引就是建立在普通字段上的索引，既不要求字段為主鍵，也不要求字段為 UNIQUE。
  • 前綴索引是指對字符型字段的前幾個字符建立的索引。使用前綴索引的目的是為了減少索引占用的存儲空間，提升查詢效率。

• 按「字段個數(shù)」分類：單列索引、聯(lián)合索引。

  • 單列索引：一個字段的索引。

  • 聯(lián)合索引：將多個字段組合成一個索引。

    • 聯(lián)合索引按照最左匹配原則，如果創(chuàng)建了一個 (a, b, c) 聯(lián)合索引，查詢條件存在a就可以匹配上聯(lián)合索引，比如where a=1；

      聯(lián)合索引的最左匹配原則會一直向右匹配直到遇到范圍查詢（>、<）就會停止使用聯(lián)合索引。也就是范圍查詢的字段可以用到聯(lián)合索引，但是在范圍查詢字段之后的字段無法用到聯(lián)合索引。注意，對于 >=、<=、BETWEEN、like 前綴匹配，這類范圍查詢，并不會停止使用索引，兩個字段都會用到聯(lián)合索引查詢，但是只是 = 的部分用到了。

    • 索引下推優(yōu)化**（index condition pushdown，ICP)， 是針對聯(lián)合索引的一種優(yōu)化。可以在聯(lián)合索引遍歷過程中，對聯(lián)合索引中包含的字段先做判斷**，直接過濾掉不滿足條件的記錄，從而減少回表次數(shù)。

      • 因為二級索引存儲字段和主鍵值，聯(lián)合索引在二級索引中的形態(tài)是存儲聯(lián)合索引中的所有字段和主鍵值。所以可以優(yōu)先對聯(lián)合索引中包含的字段先做判斷

    • 實際開發(fā)工作中在建立聯(lián)合索引時，建議把區(qū)分度大的字段排在前面，區(qū)分度越大，搜索的記錄越少。 UUID 這類字段就比較適合做索引或排在聯(lián)合索引列的靠前的位置。

      比如，性別的區(qū)分度就很小，字段的值分布均勻，那么無論搜索哪個值都可能得到一半的數(shù)據(jù)。

什么時候需要 / 不需要創(chuàng)建索引？

• 索引的缺點

  • 索引是一種數(shù)據(jù)結構，也需要占用磁盤空間。

  • 創(chuàng)建、維護索引要耗費時間，這種時間隨著數(shù)據(jù)量的增加而增大；

  • 索引有可能失效。

• 什么時候適用索引？

  • 字段有唯一性限制，比如商品編碼。
  • 經(jīng)常用于 WHERE 查詢條件、GROUP BY 和 ORDER BY 的字段。
    • 在查詢的時候就不需要再去做一次排序了，因為 B+Tree 的記錄都是有序的。

• 什么時候不需要創(chuàng)建索引？

  • WHERE 條件，GROUP BY，ORDER BY 里用不到的字段。
    • 因為索引的價值是快速定位，如果起不到定位作用的字段不需要創(chuàng)建索引。
  • 字段中存在大量重復數(shù)據(jù)，不需要創(chuàng)建索引。
    • MySQL 有一個查詢優(yōu)化器，查詢優(yōu)化器發(fā)現(xiàn)某個值出現(xiàn)在表的數(shù)據(jù)行中的百分比很高的時候，它一般會忽略索引，進行全表掃描。
  • 表數(shù)據(jù)太少的時候，不需要創(chuàng)建索引。
  • 如果字段經(jīng)常更新，不需要創(chuàng)建索引。
    • 維護B + 樹的結構，就需要頻繁重建索引，影響數(shù)據(jù)庫性能。

有什么優(yōu)化索引的方法？

• 使用前綴索引：使用字段中字符串的前幾個字符建立索引，可以減小索引字段大小，節(jié)省空間?？梢栽黾右粋€索引頁存儲前綴索引值，從而提高索引查詢速度。

  • 前綴索引的局限性

    order by 就無法使用前綴索引，因為前綴字符無法排序。

    無法把前綴索引用作覆蓋索引，因為一般只有查詢主鍵值時會用到覆蓋索引。

• 使用覆蓋索引：爭取 SQL 中查詢的所有字段，都能從二級索引中查詢得到記錄，避免回表的操作。

• 主鍵索引最好是自增的：如果我們使用主鍵自增，就不需要頻繁改變B + 樹的結構，直接按順序插入。

  • 如果我們使用非自增主鍵，每次主鍵值都是隨機的，插入新的數(shù)據(jù)時，有可能產(chǎn)生數(shù)據(jù)頁分裂，導致索引結構不緊湊，從而影響查詢效率。

• 索引列最好設置為NOT NULL（非空）約束：索引列存在 NULL 就會導致優(yōu)化器在做索引選擇的時候更加復雜，更加難以優(yōu)化。因為可為 NULL 的列會使索引、索引統(tǒng)計、值的比較，都更復雜。比如進行索引統(tǒng)計時，count 會省略值為NULL 的行。

  并且NULL 值是一個沒意義的值，行格式會至少使用1字節(jié)空間存儲NULL 值列表，會占用物理空間。

3.2 從數(shù)據(jù)頁的角度看B + 樹

數(shù)據(jù)頁的組成

InnoDB的數(shù)據(jù)是按照數(shù)據(jù)頁為單位來讀寫的，默認的大小是16KB。

數(shù)據(jù)頁由七個部分組成：文件頭（File Header）、頁頭（Page Header）、用戶空間（UserRecords） 、最大、最小記錄（Infimum + Supermum）、空閑空間（Free + Space）、頁目錄（PageDirectory）、文件尾（File Trailer）。

• 文件頭：文件頭有兩個指針，分別指向上一個和下一個數(shù)據(jù)頁，連接起來的數(shù)據(jù)頁相當于一個雙向鏈表。實現(xiàn)邏輯上的連續(xù)存儲。
• 頁目錄：頁目錄起到數(shù)據(jù)的索引作用。數(shù)據(jù)頁中的數(shù)據(jù)**按照主鍵的順序組成單向鏈表。**頁目錄由多個槽組成，**槽相當于分組數(shù)據(jù)的索引。**我們通過槽查找記錄時，可以使用二分法快速定位要查詢的記錄在哪個槽（哪個記錄分組），隨后遍歷槽內(nèi)的所有記錄，找到對應的記錄。每個槽對應的值都是這個組的主鍵最大的記錄。
• 用戶空間：在頁的 7 個組成部分中，我們自己存儲的記錄會按照我們指定的行格式存儲到 用戶空間（User Records） 部分。一開始生成頁的時候，并沒有這個部分，每當我們插入一條記錄，都會從 Free Space 部分申請一個記錄大小的空間劃分到User Records部分。當 Free Space 部分的空間全部被 User Records 部分替代掉之后，也就意味著這個頁使用完了，如果還有新的記錄插入的話，就需要去申請新的頁了。

B + 樹是如何進行查詢的？

在進行查詢時，B + 樹通過二分法快速定位到包含該記錄的頁。定位到該頁后，又會在該頁內(nèi)進行二分法快速定位記錄所在的分組（槽號），最后在分組內(nèi)進行遍歷查找。

3.3 為什么MySQL采用B + 樹作為索引？

怎樣的索引的數(shù)據(jù)結構是好的？

• 讀取數(shù)據(jù)時，先讀取索引到內(nèi)存，再通過索引找到磁盤中的某行數(shù)據(jù)，然后讀到內(nèi)存中，磁盤I/O操作次數(shù)越多，所消耗的時間也越大。所以MySQL的索引應該要盡可能減少磁盤I/O次數(shù)，并且能夠高效地查找某一個記錄，也要能高效的范圍查找。

• 為什么不用二叉查找樹？

  • 二叉查找樹的特點是一個節(jié)點的左子樹的所有節(jié)點都小于這個節(jié)點，右子樹的所有節(jié)點都大于這個節(jié)點。
  • 二叉查找樹的搜索速度快，解決了插入新節(jié)點的問題，但是如果每次插入的元素都是二叉查找樹中最大的元素，二叉查找樹就會退化成了一條鏈表，查找數(shù)據(jù)的時間復雜度變成了 O(n)。隨著元素插入越多，樹的高度越高，磁盤IO操作也就越多，查詢性能嚴重下降。

• 為什么不用自平衡二叉樹（AVL樹）？

  • 自平衡二叉樹在二叉查找樹的基礎上增加了一些條件約束：每個節(jié)點的左子樹和右子樹的高度差不能超過 1。
  • 但是和二叉查找樹一樣，隨著插入的元素變多，會導致樹的高度變高，磁盤IO操作次數(shù)就會變多，影響整體數(shù)據(jù)查詢效率。

• 為什么不用B樹？

  • B樹解決了樹的高度問題，但是B樹的每個節(jié)點都包含數(shù)據(jù)（索引+記錄），而用戶記錄的數(shù)據(jù)大小有可能遠遠超過索引數(shù)據(jù)，就要花費更多的IO來讀取到有用的索引數(shù)據(jù)。

• B + 樹對B樹進行了升級，與B樹的區(qū)別主要是以下幾點

  • 葉子節(jié)點才會存放實際數(shù)據(jù)（索引+記錄），非葉子節(jié)點只會存放索引；
  • 葉子節(jié)點之間構成一個有序鏈表，葉子結點本身依關鍵字的大小自小而大順序鏈接。對于范圍查找可以提高效率；
  • 非葉子節(jié)點的索引也會同時存在在子節(jié)點中，并且是在子節(jié)點中所有索引的最大（或最小）。
  • 非葉子節(jié)點中有多少個子節(jié)點，就有多少個索引；

• Innodb 使用的 B+ 樹有一些特別的點，比如：

  • B+ 樹的葉子節(jié)點之間是用「雙向鏈表」進行連接，這樣的好處是既能向右遍歷，也能向左遍歷。
  • B+ 樹節(jié)點的內(nèi)容是數(shù)據(jù)頁，數(shù)據(jù)頁里存放了用戶的記錄以及各種信息，每個數(shù)據(jù)頁默認大小是 16 KB。

為什么MySQL使用B + 樹作為索引？

MySQL 默認的存儲引擎 InnoDB 采用的是 B+ 樹作為索引的數(shù)據(jù)結構，原因有如下幾點：

• B+ 樹的非葉子節(jié)點僅存放索引。

  • 在數(shù)據(jù)量相同的情況下，相比既存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點的磁盤 I/O次數(shù)會更少。

• B+ 樹有大量的冗余節(jié)點。

  • 這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節(jié)點的時候，不會像 B 樹那樣會發(fā)生復雜的樹的變化；

• B+ 樹將數(shù)據(jù)按照順序存儲在葉子節(jié)點中，葉子節(jié)點之間用雙向鏈表連接，既能向右遍歷，也能向左遍歷，在排序操作和范圍查詢中有很高的效率。

  • B+Tree 存儲千萬級數(shù)據(jù)只需要 3-4 層高度就可以滿足，從千萬級的表查詢目標數(shù)據(jù)最多需要 3-4 次磁盤 I/O。
  • 而 B 樹要實現(xiàn)范圍查詢，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節(jié)點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。

綜上所述，B+樹是一種非常高效的數(shù)據(jù)結構，可以在大規(guī)模數(shù)據(jù)的情況下提供高效的索引支持，因此MySQL選擇使用B+樹作為索引。

3.4 MySQL單表不要超過2000W行，靠譜嗎？

InnoDB存儲引擎的表數(shù)據(jù)存放在一個.idb(innodb data)的文件中，也叫做表空間。

索引結構不會影響單表最大行數(shù)，2000W 也只是推薦值，超過了這個值可能會導致 B + 樹層級更高，影響查詢性能。

但是，當單表數(shù)據(jù)庫到達某個量級的上限時，導致內(nèi)存無法存儲其索引，使得之后的 SQL 查詢會產(chǎn)生磁盤 IO，從而導致性能下降，所以增加硬件配置，可能會帶來立竿見影的性能提升。

3.5 索引失效有哪些？

• 當我們使用左或者左右模糊匹配的時候，也就是 like %xx 或者 like %xx% 這兩種方式都會造成索引失效。

  • 因為索引 B+ 樹是按照「索引值」有序排列存儲的，只能根據(jù)前綴進行比較。

• 對索引列進行表達式計算、使用函數(shù)，這些情況下都會造成索引失效。

  • 因為索引保存的是索引字段的原始值，而不是經(jīng)過計算后的值。

• 索引列發(fā)生隱式類型轉換。MySQL 在遇到字符串和數(shù)字比較的時候，會自動把字符串轉為數(shù)字，然后再進行比較。如果字符串是索引列，而輸入的參數(shù)是數(shù)字的話，那么索引列會發(fā)生隱式類型轉換。

  • 由于隱式類型轉換是通過 CAST 函數(shù)實現(xiàn)的，等同于對索引列使用了函數(shù)，所以就會導致索引失效。

• 聯(lián)合索引沒有遵循最左匹配原則，也就是按照最左邊的索引優(yōu)先的方式進行索引的匹配，就會導致索引失效。

• 在 WHERE 子句中，如果在 OR 前的條件列是索引列，而在 OR 后的條件列不是索引列，那么索引會失效。

  • 因為 OR 的含義就是兩個只要滿足一個即可，只要有條件列不是索引列，就會進行全表掃描。

3.6 MySQL使用like “%x”，索引一定會失效嗎？

• 當數(shù)據(jù)庫表中的字段只有主鍵+二級索引時，使用左模糊匹配（like “%x”），不會走全表掃描（索引不會生效），而是走全掃描二級索引樹。

  • 因為查二級索引的B + 樹就可以查到全部結果，MySQL 優(yōu)化器認為直接遍歷二級索引樹要比遍歷聚簇索引樹的成本要小的多，因此 MySQL 選擇了「全掃描二級索引樹」的方式查詢數(shù)據(jù)。

• 附加題：不遵循聯(lián)合索引的最左匹配原則，索引一定會失效嗎？

  • 如果數(shù)據(jù)庫表中的字段都是索引的話，即使查詢過程中，沒有遵循聯(lián)合索引的最左匹配原則，也是走全掃描二級索引樹(type=index)。

3.7 count（*）和count（1）有什么區(qū)別？哪個性能好？

• 性能：count(*) = count(1) > count(主鍵字段) > count(字段)。

• count()是什么？

  • count()是一個聚合函數(shù)，函數(shù)的參數(shù)不僅可以是字段名，也可以是其他任意的表達式，作用是統(tǒng)計函數(shù)指定的參數(shù)不為 NULL 的記錄有多少個。

    • 比如count(name)：統(tǒng)計name不為NULL的字段有多少。

      count(1)：統(tǒng)計1不為NULL的字段有多少。1永遠不可能是NULL，所以其實是在統(tǒng)計一共有多少條記錄。

• count(主鍵字段)執(zhí)行過程是怎樣的？

  • 如果表中只有主鍵索引，沒有二級索引，InnoDB在遍歷時就會遍歷聚簇索引，將讀取到的記錄返回給server層（server層維護了一個count的變量），然后讀取記錄中的主鍵值，如果為NULL，就將count變量 + 1。

    如果表中有二級索引，InnoDB就會遍歷二級索引，通過二級索引獲取主鍵值，進一步統(tǒng)計個數(shù)。

• count(1)執(zhí)行過程是怎樣的？

  • 如果表中只有主鍵索引，沒有二級索引，InnoDB遍歷時會遍歷聚簇索引，將讀取到的記錄返回給server層，但是不會讀取記錄中的任何字段的值。因為 count 函數(shù)的參數(shù)是 1，不是字段，所以不需要讀取記錄中的字段值。如果表中有二級索引，InnoDB就會遍歷二級索引。
    • 因為 count 函數(shù)的參數(shù)是 1，不是字段，所以不需要讀取記錄中的字段值。

• count(*)執(zhí)行過程是怎樣的？

  • count(*) 其實等于 count(0)，也就是說，當你使用 count(*) 時，MySQL 會將 * 參數(shù)轉化為參數(shù) 0 來處理。

• count(字段)執(zhí)行過程是怎樣的？

  • 會采用全表掃描的方式來計數(shù)，所以它的執(zhí)行效率是比較差的。

• count(1)、 count(*)、 count(主鍵字段)在執(zhí)行的時候，如果表里存在二級索引，優(yōu)化器就會選擇二級索引進行掃描。所以，如果要執(zhí)行 count(1)、 count(*)、 count(主鍵字段) 時，盡量在數(shù)據(jù)表上建立二級索引，這樣優(yōu)化器會自動采用 key_len 最小的二級索引進行掃描，相比于掃描主鍵索引效率會高一些。

• 為什么InnoDB存儲引擎要通過遍歷索引的方式計數(shù)？

  • InnoDB 存儲引擎是支持事務的，同一個時刻的多個查詢，由于多版本并發(fā)控制（MVCC）的原因，InnoDB 表“應該返回多少行”也是不確定的。

• 如何優(yōu)化count(*) ？

  • 使用近似值。如果業(yè)務對于統(tǒng)計個數(shù)不需要很精確，可以使用explain 命令來進行估算。
  • 使用額外表保存計數(shù)值。將這個計數(shù)值保存到單獨的一張計數(shù)表中，在數(shù)據(jù)表插入一條記錄的同時，將計數(shù)表中的計數(shù)字段 + 1。但是在新增和刪除操作時，我們需要額外維護這個計數(shù)表。

分割回文串

切割問題類似組合問題。對于字符串a(chǎn)bcdef

• 組合問題：選取一個a之后，在bcdef中再去選取第二個，選取b之后在cdef中再選取第三個…。

  

• 切割問題：切割一個a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

  

class Solution {List<List<String>> ans = new ArrayList<>();Deque <String> path = new LinkedList<>();public List<List<String>> partition(String s) {StringBuffer sb = new StringBuffer(s);breaktracking(sb , 0);return ans;}void breaktracking(StringBuffer sb , int index){// 開始位置大于 sb的大小，說明找到了一組。if(index >= sb.length()){ans.add(new ArrayList<>(path));return ;}for(int i = index ; i < sb.length() ; i++){//每次切割下來的s子串。String s = sb.substring(index , i + 1);//判斷是否回文if(isBack(s)){path.add(s);}else{continue;}//切割過的位置不重復切割breaktracking(sb , i + 1);path.removeLast();}}boolean isBack(String s){StringBuffer sb = new StringBuffer(s);// System.out.println(sb.toString());if(sb.toString().equals(sb.reverse().toString())){return true;}return false;}
}

復原IP地址

截取操作都在原字符串上操作，找到一個合法stage即為：在s中當前合法stage后面加一個'.'即可。

刪除操作刪除'.'

class Solution {List<String> ans = new ArrayList<>();String stage;int pointsNum = 0;public List<String> restoreIpAddresses(String s) {if(s.length() > 12) return ans;breaktracking(s , 0);return ans;}void breaktracking(String s , int index){stage = s.substring(index);if(pointsNum == 3 && isLeagel(stage)){ans.add(s);}for(int i = index ; i < s.length() ; i++){stage = s.substring(index , i + 1);if(isLeagel(stage)){s = s.substring(0 , i + 1) + "." + s.substring(i + 1);pointsNum ++;breaktracking(s , i + 2);pointsNum -- ;s = s.substring(0 , i + 1) + s.substring(i + 2);}else break;}}boolean isLeagel(String s){if(s.length() <= 0){return false;}if(s.length() > 1 && s.charAt(0) == '0'){return false;}int num = 0;for(int i = 0 ; i < s.length() ; i ++){if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到?數(shù)字字符不合法return false;}num = num * 10 + (s.charAt(i) - '0');if (num > 255) { // 如果?于255了不合法return false;}}return true;}
}

子集

組合問題和分割問題都是手機樹的葉子節(jié)點，但是子集問題是找樹的所有節(jié)點。

遞歸終止條件：剩余集合為空，就是葉子節(jié)點，此時遞歸應該終止。

if (startIndex >= nums.size()) {return;
}

其實可以不需要加終止條件，因為startIndex >= nums.size()，本層for循環(huán)本來也結束了。

單層邏輯

for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);    // 子集收集元素backtracking(nums, i + 1);  // 注意從i+1開始，元素不重復取path.pop_back();            // 回溯
}

最終代碼如下：

class Solution {List<List<Integer>> ans = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {ans.add(new ArrayList<>(path));breaktracking(nums , 0);return ans;}void breaktracking(int [] nums , int index){if(index >= nums.length){return;}for(int i = index ; i < nums.length ; i ++){path.offer(nums[i]);//每一個節(jié)點都要加入。ans.add(new ArrayList<>(path));breaktracking(nums , i + 1);path.removeLast();}}
}

子集II

去重時，要先對集合排序，同一樹層上，不能重復選取元素。

class Solution {Deque <Integer> path = new LinkedList<>();List<List<Integer>> ans = new ArrayList<>();boolean [] used ; public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);used = new boolean [nums.length];ans.add(new ArrayList<>(path));breaktarcking(nums , 0);return ans;}void breaktarcking(int [] nums , int index){if(index >= nums.length){return;}for(int i = index ; i < nums.length ; i ++){//說明在本樹層被用過了。if( i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){continue;}path.offer(nums[i]);ans.add(new ArrayList<>(path));used[i] = true;breaktarcking(nums , i + 1);used[i] = false;path.removeLast();}}
}