LeetCode 494. Target Sum

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0);
    }
    int dfs(vector<int>& nums, int target, int pos) {
        if (pos == nums.size()) return target == 0;
        return dfs(nums, target + nums[pos], pos + 1)
            + dfs(nums, target - nums[pos], pos + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    unordered_map<string, int> m;
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0);
    }
    int dfs(vector<int>& nums, int target, int pos) {
        string key = to_string(target) + "_" + to_string(pos);
        if (m.count(key)) return m[key];
        if (pos == nums.size()) return m[key] = target == 0;
        return m[key] = dfs(nums, target + nums[pos], pos + 1)
            + dfs(nums, target - nums[pos], pos + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int n = nums.size();
        int sum = 0;
        for (auto num : nums) sum += abs(num);
        if (target > sum) return 0;
        vector<vector<int>> f(n + 1, vector<int>(2 * sum + 1));
        f[0][sum] = 1;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = -sum; j <= sum; ++j) {
                if (j - x + sum >= 0) f[i][j + sum] += f[i - 1][j - x + sum];
                if (j + x + sum <= 2 * sum) f[i][j + sum] += f[i - 1][j + x + sum];
            }
        }
        return f[n][target + sum];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int n = nums.size();
        int sum = 0;
        for (auto num : nums) sum += abs(num);
        if (target > sum || (sum - target) % 2 != 0) return 0;
        int m = (sum - target) / 2;
        vector<int> f(m + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = m; j >= 0; --j) {
                f[j] += j >= x ? f[j - x] : 0;
            }
        }
        return f[m];
    }
};