By Long Luo

Here shows 2 Approaches to slove this problem: Backtrack and Dynamic Programming.

# Backtrack

TLE

## Analysis

Time Complexity: $O(n^Sum(target))$
Space Complexity: $O(target)$

# Dynamic Programming

## Analysis

Time Complexity: $O(target * n)$
Space Complexity: $O(target)$

If the given array contains negative numbers, it will result in an infinite-length permutation.

For example, if the array $\textit{nums}$ contains positive integers $A$ and negative integers $B$ (where $A>0$, $B<0$), so there is $A \times B + A \times (-B)=0$. Which means for any permutation whose sum of elements is equal to $\textit{target}$, we can add $\textit{target} + A \times B + A \times (-B)=\textit{target}$.

Therefore, as long as there is an arrangement whose sum of elements is equal to $\textit{target}$, an arrangement of infinite length can be constructed.

If negative numbers are allowed, the maximum length of permutations must be limited to avoid infinite-length permutations before the number of permutations can be counted.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗