題目

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

答案

回溯法：

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);
}

回溯法+暫存：

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