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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    int total = 0;
    
    public int combinationSum4(int[] nums, int target) {
        total = 0;
        Arrays.sort(nums);
        backtrack(nums, target);
        return total;
    }

    private void backtrack(int[] nums, int remain) {
        if (remain == 0) {
            total++;
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > remain) {
                break;
            }

            backtrack(nums, remain - nums[i]);
        }
    }
}

Analysis

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

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 1; i <= target; i++) {
        for (int x : nums) {
            if (x > i) {
                continue;
            }

            dp[i] += dp[i - x];
        }
    }

    return dp[target];
}

Analysis

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

Follow Up

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. 😉😃💗