Leetcode — 39. Combination Sum (中文)

問題連結: https://leetcode.com/problems/combination-sum/

給予一個數字不重複的陣列candidates 以及目標總和數字target
要求回傳 利用此陣列來組成目標數字的所有組合

⚠️不限制使用各candidates elements的次數
⚠️此題要求的是組合,非排列 因此順序不重要

for candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

想法:

蠻典型的 backtracking 問題 —
我們先選一個選擇,
就開始假設 已選定這個選擇後, 其他還可以做的決定,
然後再繼續做選擇…. 直到我們不能再做決定,
則就會重做上一次選定的選擇, 這次換成另一個選擇, ...
就這樣 一直選擇 -> 選到底 -> 返回重選(undo & redo) -> 選到底 ... 直到我們把可能的情況都跑完

程式邏輯 (附解釋上述例子的backtracking圖):

前提: 我有先用內建的sorting method 排列 candidates陣列, 為的是之後我們可以快速篩選掉我們已知不可能的選擇們 (等等看例子就可以清楚知道為何要這樣做)

以下為用backtracking邏輯來解上述例子 —

先上我做的圖 -
我把它有分成幾個Level 只是為了比較好講解 可想成我們在每個Level都必須做一個選擇

Backtracking

我們用inner list來裝 現在所做的所有選擇 之後如果inner list的總和是我們要的, 我們再把它放進result list!
(A) 什麼選擇都還沒開始時, 目標是找到總和7 (💡 inner list: [])
(B) 來做第一個選擇, 選了2, 現在目標變成找到5(💡 inner list: [2])
(C) 再選一個2, 目標變成找到3(💡 inner list: [2,2])
(D) 再選2, 目標變成找到1(💡 inner list: [2,2,2])
(E) 發現所有選項都大於1, 無法繼續下去 (在這裡, 我們有4個選項, 因為我們的陣列是排序的, 因此我們光看第一個選項(i.e., 2)不合乎規定後, 我們就可以直接放心地捨棄在這之後的其他選項了)

重選我們在level D 做的選擇, 所以我們把原本在D 中最後加的選擇移掉 (💡 inner list: [2,2]), 此時目標是3
(D) 這次我們選3, target 是0 (💡 inner list: [2,2,3]) → BINGO🔥 把這個inner list加進result list裡
(E) 因為target 是0且已知陣列的數字都大於0, 代表我們可以放心結束 不再往下加數字到inner list

重選我們在level D 做的選擇, 所以我們把原本在D 中最後加的選擇移掉 (💡 inner list: [2,2]), 此時目標3
(D) 發現剩餘選項都大於3, 因此不繼續

現況: 我們已經看過所有開頭是[2,2]的inner list的可能性了.

重選我們在level C做的選擇, 所以我們把原本在C 中最後加的選擇移掉 (💡 now inner list: [2]), 此時目標5
(C) 這次 我們選3, 目標找到2. (💡 inner list:[2,3])
(D) 為了避免重複一樣的組合, 我們的選擇都只能往現在之後的找, 所以這輪我們只有三個選擇, 第一個選擇— 3 已大於目標, 因此放棄這輪

重選我們在level C做的選擇(💡 now inner list: [2]), 目標5
(C) 發現剩餘選擇皆大於目標, 放棄這輪

重選我們在level B做的選擇(💡 now inner list: []), 目標7
(B) 選3, 目標變成4. (💡 inner list: [3])
(C) 再選3, 目標變1. (💡 inner list: [3,3])
(D) 發現剩餘選擇皆大於目標, 放棄這輪

重選我們在level C做的選擇. (💡 now inner list:[3]), 目標4
(C )發現剩餘選擇皆大於目標, 放棄這輪

重選我們在level B做的選擇(💡 now inner list: []), 目標7
(B) 選6, 目標為1. (💡 inner list: [6])
(C )發現剩餘選擇皆大於目標, 放棄這輪

重選我們在level B做的選擇(💡 now inner list: []), 目標7
(B) 選7, 目標為0. (💡 inner list: [7]) → BINGO🔥 把這個inner list加進result list裡

重選我們在level B做的選擇(💡 now inner list: []), 目標7
沒有別的剩餘的選擇了 已看過全部可能的組合了😴 所以在result list裡僅有的兩個inner list即是我們最終答案

⚠️建議大家可以自己試試用別題來畫圖, 就會有更深刻印象💪

Below is the 2ms code that beats 98%:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> rst = new ArrayList<>();
        helper(rst,new ArrayList<>(),candidates,0,target);
        return rst;
    }
    public void helper(List<List<Integer>> rst, List<Integer> inner, int[] arr, int indx, int target){
        if(target==0)
        {
            rst.add(new ArrayList<>(inner));
            return;
        }
        for(int i=indx;i<arr.length;i++)
        {
            if(arr[i]>target) //eliminate unneeded paths
                return;
            inner.add(arr[i]); //select our choice
            helper(rst,inner, arr, i, target-arr[i]);
            inner.remove(inner.size()-1); //redo
        }
    }

這題的時間跟空間複雜度都很高 因為我們是真的把所有的組合都跑一遍 會是指數等級的高 😿

✏️做完這題, 也可以試著用同樣的概念來挑戰這題 78. Subsets ! 👊