aboutsummaryrefslogtreecommitdiff
path: root/target_sum.c
blob: 4b5ef9428a081acd90f7e8934e5e196ac884cccb (plain)
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
// 494. Target Sum
#include "leetcode.h"

/*
 * given an integer array 'nums' and an integer 'target'. you want to buildan
 * expression out of numbers by adding oneof the symbols '+' and '-' before each
 * integer in nums awnd then concatenate all the integers. for example if 'nums
 * = [2,1]', you can adda '+' before '2' and '-' before '1' and concatenate them
 * to build the expression '+2-1'. return the number of different
 * expressionsthat you can build, which evaluates to 'target'.
 */

int findTargetSumWays(int *nums, int numsSize, int target) {
  if (numsSize == 1) {
    if (nums[0] == target && nums[0] == -target)
      return 2;
    if (nums[0] == target || nums[0] == -target)
      return 1;
    return 0;
  }
  return findTargetSumWays(&nums[1], numsSize - 1, target + nums[0]) +
         findTargetSumWays(&nums[1], numsSize - 1, target - nums[0]);
}

int main() {
  int n1[] = {1, 1, 1, 1, 1}, n2[] = {1};
  printf("%d\n", findTargetSumWays(n1, ARRAY_SIZE(n1), 3)); // expect: 5
  printf("%d\n", findTargetSumWays(n2, ARRAY_SIZE(n2), 1)); // expect: 1
}