write a subset sum function using dynamic programming in r

Here is a dynamic programming solution to solve the subset sum problem in R:

subset_sum <- function(arr, n, sum){
  
  # Initialize the matrix to store the results
  dp <- matrix(FALSE, n+1, sum+1)

  # Base case: sum 0 can be achieved by an empty set
  for (i in 0:n) {
    dp[i+1, 0+1] <- TRUE
  }
  
  # Recursive cases
  for (i in 1:n+1) {
    for (j in 1:sum+1) {
      if (arr[i-1] > j) {
        dp[i,j] = dp[i-1,j]
      } else {
        dp[i,j] = dp[i-1,j] || dp[i-1,j-arr[i-1]]
      }
    }
  }
  
  # If subset sum is possible, return TRUE, else FALSE
  return(dp[n+1,sum+1])
}

# Example usage
arr <- c(3, 34, 4, 12, 5, 2)
sum <- 9
n <- length(arr)

subset_sum(arr, n, sum)
# Output: TRUE
625 chars
33 lines

The function subset_sum takes an input array arr, n which is the length of the array, and a sum which is the target sum that we need to find in the array. It returns a boolean value, TRUE if a subset with sum equals to sum exists, otherwise FALSE.

The algorithm works by creating a matrix dp of size (n+1) x (sum+1) where dp[i][j] represents whether the target sum j can be achieved by a subset of the first i elements of arr.

The base case of the algorithm is that a sum of 0 can always be achieved by an empty subset. For recursive cases, we first check whether the i-th element of arr is greater than the target sum j. If it is, it's impossible to form a subset that adds up to j using that element alone. So, we just copy the result for the previous row in the dp matrix. If the i-th element of arr is less than or equal to the sum j, we have two choices - either include it in the subset or exclude it. If we include it, we need to find a subset in the previous row that adds up to j-arr[i-1]. If we exclude it, we need to find a subset that adds up to j in the previous row. So, we take logical OR of these 2 possibilities and store the result in the current cell of the dp matrix.

Finally, we return dp[n+1][sum+1] as TRUE or FALSE depending on whether the target sum sum can be achieved by a subset of arr.