5月 26, 2024

Get all subset in array

這是在某個 Leetcode 裡面的某個 Easy 題目遇到的解題過程之一,也有發現直接就是要解題的題目,網路上隨便 Google 也都可以找到解法,而且解法的說明應該也很清楚,所以這篇只是記錄我自己的理解而已

本答案執行速度很慢且要跑很多次迴圈(不是遞迴!),只是相對方便理解而已

參考來源:https://www.geeksforgeeks.org/backtracking-to-find-all-subsets/

Figure 1. 

Sample code
function subsets($nums) {
        $len = count($nums);
        $sets = array();
        for ($i = 0; $i <= pow(2, $len) - 1; $i++) {
            $bin = decbin($i);
            $bin_str = str_split($bin);
            $bin_str = array_pad($bin_str, -1 * count($nums), "0");
            $subsets = array();
            foreach ($bin_str as $pos => $set_pos) {
                if ($set_pos == 1) {
                    $subsets[] = $nums[$pos];
                }
            }
            $sets[] = $subsets;
        }
        return $sets;
    }

概念是把每個位置當成取或不取的狀態,也就是 0 或 1,所以包含空集合總共會有 2^N 個結果。然後以二進制表示的話,會是 0 ~ 2^N-1 ,所以要把所有可能的組合列出來,就要跑一個 2^N 次的迴圈。

接著要把每個數字轉為二進位,這樣就會轉換成取或不取的空間,就會跟 Fig 1 一樣,但要注意的是如果直接把轉換後的數字拿來使用,方向會相反

例如

1 = 1
2 = 10

如果直接切割成陣列的話,以跑陣列順序由左到右會變成 10,所以要把他在左邊填充滿跟原始陣列長度一樣的 0 後再切割才不會有問題(我一開始寫的時候是先做切割才補 array_pad,實際上先 str_pad 會好一點)

最後就是把該串陣列跑迴圈,每個位置對應原始陣列的位置,當二進位的值為 1 時就將他放入暫存子陣列中,等 2^N 次跑完就等於取得所有的子陣列了

--

而網路上的解法用的是移位(Logical Shift)的方式,等於把拆成陣列跟跑迴圈的方式用另一個更快的方法(也更節省記憶體)去處理,但我個人對這種方式的理解能力較差所以可能只會複製來使用,然後自己用的理解方式就是這篇寫的方式。

沒有留言:

張貼留言