電子商務網(wǎng)站建設的流程百度競價排名多少錢
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ù)庫性能。
- WHERE 條件,GROUP BY,ORDER BY 里用不到的字段。
有什么優(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,不是字段,所以不需要讀取記錄中的字段值。
- 如果表中只有主鍵索引,沒有二級索引,InnoDB遍歷時會遍歷聚簇索引,將讀取到的記錄返回給server層,但是不會讀取記錄中的任何字段的值。因為 count 函數(shù)的參數(shù)是 1,不是字段,所以不需要讀取記錄中的字段值。如果表中有二級索引,InnoDB就會遍歷二級索引。
-
count(*)執(zhí)行過程是怎樣的?
- count(
*
) 其實等于 count(0
),也就是說,當你使用 count(*
) 時,MySQL 會將*
參數(shù)轉化為參數(shù) 0 來處理。
- count(
-
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();}}
}