我們接續上一篇：

【從面試題學邏輯-16】拔智齒可以不要寫鐵人賽嗎？好像不能這樣做诶（leetcode 78. Subsets）

這是這題的遞迴解法，所以題目我們不再重述，還沒看過上一篇請先去閱讀一下喔

那這題要怎麼用遞迴呢？我們的步驟如下：

1. 設定一個終止條件，把空List丟回去
2. 把上一步拿到的subsets，分別加入這一步要加的元素
3. 把新產生的newSubsets塞進去subsets

見下圖GIF

簡而言之，就是拿到新的數字後，把舊的東西拿出來，把這個新的東西塞進去。這樣就會有新的subset產生，把新的subset塞進去subsets再繼續下一步。

我們先看程式碼

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        return getSubsets(nums, 0);
    }
    
    public List<List<Integer>> getSubsets(int[] set, int index){
        List<List<Integer>> subsets;
        if (set.length == index) {
            subsets = new ArrayList<List<Integer>>();
            subsets.add(new ArrayList<Integer>());
        } else {
            subsets = getSubsets(set, index+1);
            int element = set[index];
            List<List<Integer>> newSubsets = new ArrayList<List<Integer>>();
            for(List<Integer> s : subsets) {
                List<Integer> newSubset = new ArrayList<Integer>();
                for(Integer n: s) {
                    newSubset.add(n);
                }
                newSubset.add(element);
                newSubsets.add(newSubset);
            }
            for(List<Integer> s : newSubsets) {
                subsets.add(s);
            }
        }
        return subsets;
    }
}

接下來逐一講解一下：

public List<List<Integer>> subsets(int[] nums) {
    return getSubsets(nums, 0);
}

這一步就是呼叫我們新寫的遞迴方法

public List<List<Integer>> getSubsets(int[] set, int index{
    // 暫時省略中間
}

好，我們知道set就是原本的nums，那這個index是幹嘛用的呢？
上面我們說到要逐一把東西塞進去，這個index就是告訴程式「這一步要拿set中第幾個數字出來處理」

if (set.length == index) {
    subsets = new ArrayList<List<Integer>>();
    subsets.add(new ArrayList<Integer>());
}

這就是終止條件，大家記得子集包含一個空（{}）嗎？，所以index等於set長度時，我們給他一個空來做為終止條件。

subsets = getSubsets(set, index+1);

如果index不為set長度，我們就拿index+1的subset回來做處理（也就是說會一路先拿到空再開始處理）

int element = set[index];
List<List<Integer>> newSubsets = new ArrayList<List<Integer>>();

接下來我們把要處理的數字拿出來，並且開一個大的List存等等加完數字的subset

for(List<Integer> s : subsets) {
    List<Integer> newSubset = new ArrayList<Integer>();
    for(Integer n: s) {
        newSubset.add(n);
    }
    newSubset.add(element);
    newSubsets.add(newSubset);
}

我們先開一個newSubset的List，然後把已經拿到的subsets中，分別把subset內的數字拿出來，加進newSubset中。接著再把這一次要加進去的數字，加到newSubset中，就可以獲得一個新的subset。

for(List<Integer> s : newSubsets) {
    subsets.add(s);
}

最後我們把所有找到的subsets往回丟，解決！

這一題用遞迴需要再多自行想想過程，因為遞迴本身就是一個需要思考+想像的東西，把最上面的GIF搭配程式碼，能夠更好的幫大家釐清過程喔！

個人原本是用JavaScript寫，像這樣：

結果換成Java就變成很長一串……真是可怕