2597. The Number of Beautiful Subsets 解題紀錄

這題要我解出 List 裡面所有子集合，但是裡面的任意元素差不能等於 K。理論上跟前幾天的編碼一樣，最多的子集合數為 2^N -1。（因為這題不接受空集合為答案，要減去。)

所以我們先用一個 DP Matrix 紀錄哪兩個點進入子集時，這個子集就為非法不能存進答案。再用 DFS 推出所有子集，當合法時就存入答案。如果想偷一下時間可以跟我一樣做全尺寸的 DP Matrix，想省記憶體的話可以當場推不要做 DP。

程式碼：

後記：雖然我看了大家省記憶體都省到極限了，在放風的時候畫了一下這題能不能用文氏圖解？這樣就可以省下 CurrList 的記憶體空間。畢竟 DP Matrix 就像是一個條件圖，但是不行，文氏圖只能推到六個集合，而這題的測資長度 <= 16，代表有可能解到十六個集合，以上 O口O！