Python and Rust Push DP vs Pull DP (with HashMap and Array)
IntuitionWe use a hash map to store the sum of numbers encountered so far and the count of times each sum has been reached. Initially, the hash map contains {0:
## Intuition

We use a **hash map** to store the sum of numbers encountered so far and the count of times each sum has been reached. Initially, the hash map contains `{0: 0}`, indicating that a sum of `0` is possible with `0` elements. As we iterate through the numbers, we update the hash map by adding the current number to existing sums and keeping track of the highest count for each sum.

### Advantages of Hash Map Approach
- **Memory Efficient**: We do not store all numbers from `0` to `target`.
- **Limitations in Python**: Since we can't modifying a dictionary while iterating, we use a `new_dict` to update the values. which is also a cost of memory so we will need to consider this as well when considering.

## Code Using Hash Map
```python []
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        seen = {0: 0}  # Stores sum -> count of elements used
        
        for num in nums:
            new_dict = {}
            for prev_sum, length in seen.items():
                next_num = prev_sum + num
                if next_num > target:
                    continue
                new_dict[next_num] = max(seen.get(next_num, 0), length + 1)
            
            seen.update(new_dict)
        
        return seen[target] if target in seen else -1
```
```rust []
use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {
        let mut seen: HashMap<i32, i32> = HashMap::new();
        seen.insert(0, 0);

        for &num in nums.iter() {
            let mut updated_vals = HashMap::new();
            for (&prev_sum, &length) in seen.iter() {
                let next_sum = prev_sum + num;
                if next_sum > target {
                    continue;
                }
                let prev_in_seen: i32 = seen.get(&next_sum).copied().unwrap_or(0);
                updated_vals.entry(next_sum).or_insert(prev_in_seen.max(length + 1));
            }
            seen.extend(updated_vals);
        }

        *seen.get(&target).unwrap_or(&-1)
    }
}
```


## Dynamic Programming Approach
The DP approach is generally faster but requires allocating an array from `0` to `target`.

### Push DP vs Pull DP
There are two ways to update the DP table:

### 1. Push DP (Forward Update)
In **push DP**, we update future indices based on the current value.

#### Implementation
```python []
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        dp = [float('-inf')] * (target + 1)
        dp[0] = 0
        
        for num in nums:
            for i in range(target - num, -1, -1):  # Push forward
                dp[i + num] = max(dp[i + num], dp[i] + 1)
                
        return dp[target] if dp[target] != float('-inf') else -1
```
```rust []
use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {
        let mut dp = vec![i32::MIN; (target + 1) as usize];
        dp[0] = 0;

        for &num in nums.iter() {
            for i in (0..=target - num).rev() {
                let future_idx = (i + num) as usize;
                dp[future_idx] = dp[future_idx].max(dp[(i) as usize] + 1);
            }
        }
        
        if dp[target as usize] < 0{
            return -1;
        }

        dp[target as usize]
    }
}
```

#### Explanation:
- Iterate over the numbers.
- For each `num`, update `dp[i + num]` using `dp[i]`.
- This ensures that `dp[i + num]` gets updated only after `dp[i]` has been processed.

### 2. Pull DP (Backward Update)
In **pull DP**, we update the current index by looking at past computed values.

#### Implementation
```python []
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        dp = [float('-inf')] * (target + 1)
        dp[0] = 0
        
        for num in nums:
            for i in range(target, num - 1, -1):  # Pull from previous values
                dp[i] = max(dp[i], dp[i - num] + 1)
                
        return dp[target] if dp[target] != float('-inf') else -1
```
```rust []
use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {
        let mut dp = vec![i32::MIN; (target + 1) as usize];
        dp[0] = 0;

        for &num in nums.iter() {
            for i in (num..=target).rev() {
                dp[i as usize] = dp[i as usize].max(dp[(i - num) as usize] + 1);
            }
        }

        if dp[target as usize] < 0{
            return -1;
        }

        dp[target as usize]
    }
}
```

#### Explanation:
- Iterate over the numbers.
- Instead of pushing forward, `dp[i]` is updated based on `dp[i - num]`.
- Ensures that all previous calculations are stable before updating `dp[i]`.




['Array', 'Hash Table', 'Dynamic Programming', 'Python3', 'Rust']