Your solution computes all possible target sums that are obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers. For an array with \$n\$ numbers that are \2ドル^n\$ combinations.
This is a typical case where dynamic programming is of advantage. Instead of searching for all combinations which lead to the target sum \$S\$, one computes the number of combinations leading to any target sum in a range.
The crucial hint here is
- The sum of elements in the given array will not exceed 1000.
which means that only target sums between \$-1000\$ and \1000ドル\$ can be obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers, that are "only" \2001ドル\$ possible target sums.
So the idea is to maintain a list L of length \2001ドル\$, corresponding to the possible target sums \$-1000 \ldots 1000\$. At each point in the following iteration L[i + 1000] is the number of ways to obtain the target sum i with the numbers encountered so far.
Initially, L[1000] = 0 and all other entries are zero, because 0 is the only target sum that can be obtained using none of the numbers.
Then you iterate over the given array of numbers and update the list L.
Ultimately, L[S + 1000] is the wanted number of ways to obtain the target sum S using all the given numbers.
This approach has \$ O(n) \$ time complexity, which is asymptotially much better than \$O(2^n)\$ of your original approach.
Your solution computes all possible target sums that are obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers. For an array with \$n\$ numbers that are \2ドル^n\$ combinations.
This is a typical case where dynamic programming is of advantage. Instead of searching for all combinations which lead to the target sum \$S\$, one computes the number of combinations leading to any target sum in a range.
The crucial hint here is
- The sum of elements in the given array will not exceed 1000.
which means that only target sums between \$-1000\$ and \1000ドル\$ can be obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers, that are "only" \2001ドル\$ possible target sums.
So the idea is to maintain a list L of length \2001ドル\$, corresponding to the possible target sums \$-1000 \ldots 1000\$. At each point in the following iteration L[i + 1000] is the number of ways to obtain the target sum i with the numbers encountered so far.
Initially, L[1000] = 0 and all other entries are zero, because 0 is the only target sum that can be obtained using none of the numbers.
Then you iterate over the given array of numbers and update the list L.
Ultimately, L[S + 1000] is the wanted number of ways to obtain the target sum S using all the given numbers.
This approach has \$ O(n) \$ complexity, which is asymptotially much better than \$O(2^n)\$ of your original approach.
Your solution computes all possible target sums that are obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers. For an array with \$n\$ numbers that are \2ドル^n\$ combinations.
This is a typical case where dynamic programming is of advantage. Instead of searching for all combinations which lead to the target sum \$S\$, one computes the number of combinations leading to any target sum in a range.
The crucial hint here is
- The sum of elements in the given array will not exceed 1000.
which means that only target sums between \$-1000\$ and \1000ドル\$ can be obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers, that are "only" \2001ドル\$ possible target sums.
So the idea is to maintain a list L of length \2001ドル\$, corresponding to the possible target sums \$-1000 \ldots 1000\$. At each point in the following iteration L[i + 1000] is the number of ways to obtain the target sum i with the numbers encountered so far.
Initially, L[1000] = 0 and all other entries are zero, because 0 is the only target sum that can be obtained using none of the numbers.
Then you iterate over the given array of numbers and update the list L.
Ultimately, L[S + 1000] is the wanted number of ways to obtain the target sum S using all the given numbers.
This approach has \$ O(n) \$ time complexity, which is asymptotially much better than \$O(2^n)\$ of your original approach.
Your solution computes all possible target sums that are obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers. For an array with \$n\$ numbers that are \2ドル^n\$ combinations.
This is a typical case where dynamic programming is of advantage. Instead of searching for all combinations which lead to the target sum \$S\$, one computes the number of combinations leading to any target sum in a range.
The crucial hint here is
- The sum of elements in the given array will not exceed 1000.
which means that only target sums between \$-1000\$ and \1000ドル\$ can be obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers, that are "only" \2001ドル\$ possible target sums.
So the idea is to maintain a list L of length \2001ドル\$, corresponding to the possible target sums \$-1000 \ldots 1000\$. At each point in the following iteration L[i + 1000] is the number of ways to obtain the target sum i with the numbers encountered so far.
Initially, L[1000] = 0 and all other entries are zero, because 0 is the only target sum that can be obtained using none of the numbers.
Then you iterate over the given array of numbers and update the list L.
Ultimately, L[S + 1000] is the wanted number of ways to obtain the target sum S using all the given numbers.
This approach has \$ O(n) \$ complexity, which is asymptotially much better than \$O(2^n)\$ of your original approach.