backTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
backTrack(nums, target, 0, 0);
return ret;
}
private:
int ret = 0;
void backTrack(vector<int>& nums, int target, int cur, int i)
{
if(i >= nums.size())
{
if(cur == target)
++ret;
return;
}
backTrack(nums, target, cur + nums[i], i + 1);
backTrack(nums, target, cur - nums[i], i + 1);
}
};
|
hashmap
本质上是用hash来代替递归操作，实际上还是走遍了分支 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) {
unordered_map<int, int> map;
map[nums[0]] += 1;
map[-nums[0]] += 1;
for(int i = 1; i < nums.size(); ++i)
{
unordered_map<int, int> tmp;
for(auto& it : map)
{
tmp[it.first + nums[i]] += it.second;
tmp[it.first - nums[i]] += it.second;
}
map = tmp;
}
return map[target];
}
};
|
看官方题解
dp{i][j]表示前i个数字能构成和为j的方案数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int diff = accumulate(nums.begin(), nums.end(), 0) - target;
if(diff < 0 || diff & 1)
return 0;
int neg = diff >> 1;
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
int num = nums[i - 1];
for(int j = 0; j <= neg; ++j)
{
dp[i][j] = dp[i - 1][j];
if(num <= j)
dp[i][j] += dp[i - 1][j - num];
}
}
return dp[n][neg];
}
};
|
优化空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int diff = accumulate(nums.begin(), nums.end(), 0) - target;
if(diff < 0 || diff & 1)
return 0;
int neg = diff >> 1;
int n = nums.size();
vector<int> dp(neg + 1);
dp[0] = 1;
for(int i = 1; i <= n; ++i)
{
int num = nums[i - 1];
for(int j = neg; j >= 0; --j)
{
dp[j] = dp[j];
if(num <= j)
dp[j] += dp[j - num];
}
}
return dp[neg];
}
};
|