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）的方式，等於把拆成陣列跟跑迴圈的方式用另一個更快的方法（也更節省記憶體）去處理，但我個人對這種方式的理解能力較差所以可能只會複製來使用，然後自己用的理解方式就是這篇寫的方式。