subsetSum function

bool subsetSum(List<int> nums, int target)

🔢 Subset Sum (Dynamic Programming)

Returns true if there exists a subset of nums that sums to target.

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

Implementation

bool subsetSum(List<int> nums, int target) {
  final dp = List<bool>.filled(target + 1, false);
  dp[0] = true;
  for (final num in nums) {
    for (int t = target; t >= num; t--) {
      if (dp[t - num]) dp[t] = true;
    }
  }
  return dp[target];
}