[494] Target Sum

啊～為什麼不能從前面往後面做呢～都西爹QQ

據說是, 因為數字可以有+號和-號的差別，可以想成有加號的叫做set S1 , 減號的叫做set S2

所以,

S1 + S2 = sum

S1 - S2 = target

數學運算式  XD 兩者相加, 

2S1 = sum + target

S1 = (sum+ taregt) /2

所以要求的就變成，哪些數字可以組成S1 了！！！

int findTargetSumWays(int* nums, int numsSize, int target) {

int sum=0;

for (int i=0; i<numsSize; i++)

sum+=nums[i];

if (((sum+target)%2 !=0) || (target > sum) || (target < sum*(-1)))

return 0;

int new_target = (sum+target)/2;

int *dp = calloc (new_target+1, sizeof(int));

dp[0]=1;

for (int i=0; i<numsSize; i++)

{

for (int j=new_target; j>= nums[i]; j--)

dp[j]= dp[j]+ dp[j-nums[i]];

}

return dp[new_target];

}

看到別人有recursive 寫法，依樣畫葫蘆一番 QQ

int findTargetSumWays(int* nums, int numsSize, int target) {

if (numsSize == 1)

{

if (nums[0]== target && nums[0] == -target)

return 2;

else if (nums[0]== target || nums[0] == -target)

return 1;

else

return 0;

}

return findTargetSumWays(nums, numsSize-1, target-nums[numsSize-1])+ findTargetSumWays(nums, numsSize-1, target+nums[numsSize-1]);

}