Leetcode — 39. Combination Sum (中文)

6 min readDec 31, 2020

問題連結: 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都必須做一個選擇

我們用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 ! 👊

Leetcode — 39. Combination Sum (中文)

想法:

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

Written by Anj