iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 18
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 18

【從面試題學邏輯-18】用遞迴找子集似乎把事情搞得更難懂了……(leetcode 78. Subsets)

我們接續上一篇:

【從面試題學邏輯-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搭配程式碼,能夠更好的幫大家釐清過程喔!/images/emoticon/emoticon22.gif

個人原本是用JavaScript寫,像這樣:

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


上一篇
【從面試題學邏輯-17】找一個不會影分身的傢伙怎麼這麼討人厭?(leetcode 137. Single Number II)
下一篇
【從面試題學邏輯-19】幫你自己次方一下(leetcode 50. Pow(x, n))
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言