using System;

using System.Collections.Generic;

public class Program

{

    //Recursive with cache - runtime: worst case 2*someOfNums*i cache misses - so O(someOfNums*i) - we only have to compute each value once, 

    //and space: O(someOfNums*i) - size of cache (bigger than stack size)

    private static int TargetSum(int[] nums, int T, int i, Dictionary<Tuple<int,int>, int> cache){

        if (i == nums.Length){

            if (T == 0) {

                return 1;

            } else return 0;

        }

        var targetPositionPair = new Tuple<int,int>(T,i);

        if (cache.ContainsKey(targetPositionPair)){

            //Console.WriteLine("Found " + "target: " + T + " position: " + i);

            return cache[targetPositionPair];

        }

        var waysAfterAdding = TargetSum(nums, T - nums[i], i + 1, cache);

        var waysAfterSubtracting = TargetSum(nums, T + nums[i], i + 1, cache);

        var totalWays = waysAfterAdding + waysAfterSubtracting;

        //Console.WriteLine("Added " + "target: " + T + " position: " + i);

        cache.Add(targetPositionPair, totalWays);

        return totalWays;

    }

    public static int TargetSum(int[] nums, int T){

        var cache = new Dictionary<Tuple<int,int>, int>();

        return TargetSum(nums, T, 0, cache);

    }

    //NOT WORKING

    //Iterative with cache - runtime: , and space:

    private static int TargetSum2(int[] nums, int T){

        var maxNumsSum = 0;

        var minNumsSum = 0;

        foreach(var num in nums){

            maxNumsSum += Math.Abs(num);

            minNumsSum -= Math.Abs(num);

        }

        //maxNumsSum = -minNumsSum

        if (maxNumsSum == 0) return 0;

        var cache = new int[(2*maxNumsSum)+1, nums.Length+1];

        var offset = maxNumsSum;

        //initialize base case

        //cache[-nums[0]+offset,0] = 1;

        //cache[nums[0]+offset,0] = 1;

        cache[offset,0]=1;

        //Console.WriteLine("Hi");

        //iterate column by column

        for(var i=1; i<cache.GetLength(1); i++){ 

            for(var t=0; t<cache.GetLength(0); t++){

                //Console.WriteLine("Hi");

                //added

                //cache[t-nums[i-1]+offset,i] += cache[t,i-1];

                //subtracted

                //cache[t+nums[i-1]+offset,i] += cache[t,i-1];

                var ways = 0;

                if (t-nums[i-1]+offset >= 0 && t-nums[i-1]+offset < (2*maxNumsSum)+1){

                    ways += cache[t-nums[i-1]+offset,i-1];

                }

                if (t+nums[i-1]+offset >= 0 && t+nums[i-1]+offset < (2*maxNumsSum)+1){

                    ways += cache[t+nums[i-1]+offset,i-1];

                }

                if (t+offset >= 0 && t+offset < (2*maxNumsSum)+1){

                    cache[t+offset,i]=ways;

                }

                //cache[t+offset,i] = cache[t-nums[i-1]+offset,i-1]+cache[t+nums[i-1]+offset,i-1];

            }

        }

        var wantedIndexedT = T+offset;

        return cache[wantedIndexedT, nums.Length];

    }

    public static void Main()

    {

        var nums = new int[]{1,1,2,3};

        var T = 1;

        Console.WriteLine(TargetSum(nums,T));

        Console.WriteLine(TargetSum2(nums,T));

    }

}