[C#][LeetCode] 494. Target Sum

題目

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and – as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

題目會傳入兩個參數 nums (數字陣列)S (整數),限制只能使用兩個運算符號 +- 改變數字陣列 nums 的數字讓總和等於 S

解題過程

我自己比較少接觸演算法的東西(大學沒學好),就算去翻解答也看不懂別人在寫什麼東西,後來看了 演算法筆記- Backtracking 的圖解後終於理解解答再寫什麼東西

答案

回溯法:

 

回溯法+暫存:

 

原始碼:GitHub

參考資料

  1. TargetSum
  2. 演算法筆記- Backtracking