LeetCode中的Combination Sum IV 這題我最後沒有解出來，之前在刷LeetCode的題目時，還是會常常想要依靠自己的腦袋去解題，所以會用很直觀的方式去思考，但隨著接觸到的題目越來越難，有些思路真的是會需要先參考他人的答案才有可能去做解答，對於第一個想出來的人真的很佩服，廢話不多說，來看題目吧！
LeetCode Combination Sum IV 題目詳解
老樣子，中文翻譯為給定一個陣列和一個目標數字，找出陣列內的元素加總等於目標數字的方法總共有幾個，並且不同位置的組合也要算進去，也就是[1,3]和[3,1]是不一樣的。
首先這題的困難點在於，直觀想法是很難去轉換成程式的，也就是你在現實中給你紙和筆你怎麼解答這題，你其實是沒有規律的一直湊數字，很難有一個統整的想法出來，所以我最後也是卡在這裡就敗倒了，接下來我就來把我理解過後他人的解題方法思路來做詳解，這邊放上思路的出處
https://blog.csdn.net/fuxuemingzhu/article/details/79343825
首先我們必須要先從一個點去思考，
假設我們能夠知道這個陣列中組合成1,2,3的可能性有多少個，我們便可以去繼續4（target）的組合有多少個
什麼意思呢？ 4有以下幾個組合 0+4 / 1+3 / 2+2 / 3+1 / 4+0 而首先我們先不考慮前後兩者，因為4並不存在於陣列內，則我們思考一下 以1+3來說，3的組合我們發現有4個所以 1*4 = 4 ，而2+2的組合我們發現2的組合有2個，1*2乙次類推最後就會得到4的組和有7個也就是正確答案，可能會有同學問說
1+3不應該是 1的組合+3的組合嗎？
這邊我們要思考的是，如果前面那個數字也放進去做組合的話，則答案就會重複譬如 2+2拆成 1+1+1+1 ＝而 1+3也同樣拆成1+1+1+1則這樣就沒有意義了，反而如果前面的數字不能懂的話，則從順序上是得不到重複的答案的，
那我們要怎麼去算組合呢？這邊我們就可以來看程式碼
dp = [0] * (target + 1)
dp[0] = 1
首先我們先宣告一個數組dp，其意義為dp[i]就是代表i有多少種陣列組合
for i in range(1, target + 1):
for num in nums:
if i >= num:
#dp[1] = dp[0]
#dp[2] = dp[2]+dp[2-1]
#dp[2] = dp[2]+dp[2-2]
#dp[3] = dp[3]+dp[3-1]
#dp[3] = dp[3]+dp[3-2]
#dp[3] = dp[3]+dp[3-3]
dp[i] += dp[i - num]
return dp.pop()
此處我們可以來觀察一下他是如何計算的，首先i的range代表去遍歷1~target，再來num則是陣列內的元素，而每當i>=num，也就是說num有可能組合成i的時候，這邊讓dp[i] = dp[i] + dp[i-num]，是什麼意思呢？我們思考剛剛說的，以dp[3]為例子，當遇到num = 1時，我們可以將組合想像成 1+2，所以只要將dp[3-1]=2的組合可能數目就會是dp[3]的可能數目，而再來當num=2時，組合就會變成2+1，所以只要加入dp[3-2] =1的組合可能數目，也會是dp[3]的可能數目，到最後則是num =3 時，加入dp[0]的可能數目，這三者加總就會是dp[3]的全部可能數目，最後類推到dp[4]就會得到答案了。
這題在思考上真的很難單純用直觀方法想出來，我覺得屬於你必須要持續刷LeetCode有一定的解題經驗才能想出來的題目，那今天的講解就到這裡！