题目大意：给你一串数字，你可以在每个数字前放置+或-，问有多少种方法可以使得表达式的值等于target。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.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Idea: DP

Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S) return 0;

const int offset = sum;

// ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].

vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0));

ways[0][offset] = 1;

for (int i = 0; i < n; ++i) {

for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j)

if (ways[i][j]) {

ways[i + 1][j + nums[i]] += ways[i][j];

ways[i + 1][j - nums[i]] += ways[i][j];

}

return ways.back()[S + offset];

}

};

C++ SC O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = num; i < kMaxN - num; ++i)

if (ways[i]) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < S) return 0;

final int kOffset = sum;

final int kMaxN = sum * 2 + 1;

int[] ways = new int[kMaxN];

ways[kOffset] = 1;

for (final int num : nums) {

int[] tmp = new int[kMaxN];

for (int i = num; i < kMaxN - num; ++i) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

ways = tmp;

}

return ways[S + kOffset];

}

C++ / V2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = 0; i < kMaxN; ++i) {

if (i + num < kMaxN) tmp[i] += ways[i + num];

if (i - num >= 0) tmp[i] += ways[i - num];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 422 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

int ans = 0;

dfs(nums, 0, S, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int d, int S, int& ans) {

if (d == nums.size()) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d], ans);

dfs(nums, d + 1, S + nums[d], ans);

}

};

Java

// Author: Huahua

// Running time: 615 ms

class Solution {

private int ans;

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < Math.abs(S)) return 0;

ans = 0;

dfs(nums, 0, S);

return ans;

}

private void dfs(int[] nums, int d, int S) {

if (d == nums.length) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d]);

dfs(nums, d + 1, S + nums[d]);

}

Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

C++ w/ copy

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums) {

vector<int> tmp(dp);

for (int j = 0; j <= target - num; ++j)

tmp[j + num] += dp[j];

std::swap(dp, tmp);

}

return dp[target];

}

};

C++ w/o copy

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums)

for (int j = target; j >= num; --j)

dp[j] += dp[j - num];

return dp[target];

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏

花花酱 LeetCode 494. Target Sum

Idea: DP

Solution 1: DP

C++

C++ SC O(n)

Java

C++ / V2

Solution 2: DFS

C++

Java

Solution 3: Subset sum

C++ w/ copy

C++ w/o copy

Be First to Comment

Leave a Reply Cancel reply