Problem statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.
Link to problem

Example 1

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2

Input: nums = [9], target = 3
Output: 0

Solutions

Approach 1: Dynamic Programming - Iterative

Truth be told, I struggled with this and didn’t really understand what NeetCode was trying to convey, another reason his approaches seem off is because he does it backwards and I feel like that just adds a few steps while implementing them in Rust.
Sure it’s easier in Python but it isn’t as easy across other languages. After a brief ahem research, I’ve found a way that actually made sense, I’m sure NeetCode’s way was exactly the same but backwards.

What we’re trying to do:
Count the number of ways in which a particular target can be formed given a list.

How to approach it: We check every number from 1 until target, and see how many ways there are when compared with the numbers available in list.

Like usual with DP, an example might be the easiest way to understand this.

Given nums=[1,2,3] and target=4

target = 1
    combinations = [1]

target = 2
    combinations = [[1,1], 2] (include all combinations until this point, which is the previous combination + 1)

target = 3
    combinations = [[1,1,1], [1,2], [2,1], 3]
...

Implementation in Rust

fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
    let mut result = vec![0; target as usize + 1];
    for i in 1..(target + 1) {
        for num in nums.iter() {
            if i == *num {
                result[i as usize] += 1
            }
            if i > *num {
                result[i as usize] += result[i as usize - *num as usize]
            }
        }
    }
    result[target as usize]
}

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
Runtime on LeetCode: $1$ms

Honorable Implementation

The following solution is implemented using Rust’s powerful iterators by my good friend, binds.

fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
    (1..=target).fold(vec![1], |mut v, x| {
        v.push(
            nums.iter()
                .filter(|&num| x >= *num)
                .fold(0, |acc, &num| acc + v[(x - num) as usize]),
        );
        v
    })[target as usize]
}

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
Runtime on LeetCode: $3$ms