By Long Luo

This article is the solution 2 Approaches: Backtrack and DP with Follow Up Analysis of Problem 377. Combination Sum IV.

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

# Backtrack

The Backtrack will be a complete search and its time complexity will be $$O(2^n)$$.

Surely it will be TLE!

## Analysis

• Time Complexity: $$O(2^n)$$
• Space Complexity: $$O(\textit{target})$$

# Dynamic Programming

## Analysis

• Time Complexity: $$O(\textit{target} \times n)$$
• Space Complexity: $$O(\textit{target})$$

#### What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

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 \gt 0$$, $$B \lt 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. 😉😃💗