今天的題目是LeetCode 第三十九題Combination Sum，題目是給你一個整數陣列和一個目標值，你要找出所有加總等於目標值的數字組合，而且陣列裡的每個數字可以被重複使用不限次數。輸出的結果要是一個所有組合的清單，每個組合內的數字相加都要剛好等於目標。這段程式在做的事情其實就是用回溯法一個一個去嘗試組合。一開始我們有一個目標數字target，程式會從候選數字陣列candidates 的第一個開始試。每次有兩種選擇：跳過這個數字，去看下一個；或是 選這個數字，把它加進目前的組合裡，然後繼續嘗試看看還能不能湊出目標值。當目前加總剛好等於目標值的時候，就把這個組合存進結果裡；如果加總超過目標值，就回頭不再繼續這條路。因為數字可以重複選，所以選了某個數字之後，還可以繼續在同一個位置嘗試。程式就是靠這樣不停地「選或不選」，列舉出所有可能的組合，最後把符合的全部回傳。
iThome鐵人賽
看影片追技術