[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 的圖解後終於理解解答再寫什麼東西

答案

回溯法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int FindTargetSumWays(int[] nums, int S)
{
int sum = nums.Sum();
return Calculate(nums, 0, S, sum);
}

static int Calculate(int[] nums, int idx, int targetSum, int sum)
{
if (idx == nums.Length)
{
return (targetSum == 0) ? 1 : 0;
}
// 數字加總 如果小於 目標加總 就不用跑後面的列舉
else if (sum < targetSum)
{
return 0;
}

int nextIdx = idx + 1;
return Calculate(nums, nextIdx, targetSum + nums[idx], sum) +
Calculate(nums, nextIdx, targetSum - nums[idx], sum);
}

回溯法+暫存:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static int FindTargetSumWays2(int[] nums, int S)
{
int sum = nums.Sum();

// 利用快取的方式減少重複運算
int[][] cache = new int[nums.Length][];
for (int i = 0; i < cache.Length; i++)
{
cache[i] = new int[(2 * sum) + 1];
Array.Fill(cache[i], -1);
}

return Calculate2(nums, 0, S, sum, cache);
}

static int Calculate2(int[] nums, int idx, int targetSum, int sum, int[][] cache)
{
if (idx == nums.Length)
{
return (targetSum == 0) ? 1 : 0;
}
// 數字加總 如果小於 目標加總 就不用跑後面的列舉
else if (sum < targetSum)
{
return 0;
}

int nextIdx = idx + 1;

if (cache[idx][sum + targetSum] < 0)
{
cache[idx][sum + targetSum] =
Calculate2(nums, nextIdx, targetSum + nums[idx], sum, cache) +
Calculate2(nums, nextIdx, targetSum - nums[idx], sum, cache);
}

return cache[idx][sum + targetSum];
}

原始碼:GitHub

參考資料

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