CODEWITHSUNDEEP
rfunctionrecursion
Corel
Corel

Reputation: 633

combinations of numbers to reach a given sum - recursive implementation in R

All I want to do is to implement the solution given here (the one in python) in R. I'm not very used to do debugging in R-Studio but even after I have tried that I still can't figure out why my code does not work. Basically (with the example input provided) I get the function to run over all the numbers and then it is stuck in a sort of infinite loop (or function). Can someone please point me in the right direction regarding this?

subset_sum <- function(numbers, target, partial = numeric(0)){
  s <-  sum(partial,na.rm = TRUE)

  # check if the partial sum equals to target
  if (s == target){
    cat("sum(",partial,")","=",target)
  }
  else if (s >= target) {
    return() # if we reach the number why bother to continue

  }
  else {

    for(i in 1:length(numbers)){
      n <-  numbers[i]
      remaining <- numbers[i+1:length(numbers)]
      subset_sum(remaining, target, partial = append(partial,n))
    }
      }
}

subset_sum(c(3,9,8,4,5,7,10),15)

When not run in debug mode it gives me these errors:

Error: node stack overflow
Error during wrapup: node stack overflow

Upvotes: 0

Views: 614

Answers (2)

CPak
CPak

Reputation: 13581

This is not a recursive function but it takes advantage of R's ability to handle matrix/array type data. Some output is shown after #

v <- c(3,9,8,4,5,7,10)
v <- sort(v)
# [1]  3  4  5  7  8  9 10
target <- 15
# we don't need to check more than at most 4 numbers since 3+4+5+7 (the smallest numbers) is greater than 15
mincombs <- min(which(cumsum(v) > target))  
# [1] 4
Combs <- combn(v, mincombs)  # make combinations of numbers
ans <- mapply(function(x,y) ifelse(y > 0, paste0(paste0(Combs[1:y,x], collapse="+"), "=", target), NA), 1:ncol(Combs), apply(Combs, 2, function(I) which(cumsum(I) == target)))
ans <- unlist(ans[lengths(ans) > 0])
# [1] "3+4+8=15" "3+4+8=15" "3+5+7=15" "3+5+7=15" "3+5+7=15" "7+8=15"

In a function

myfun <- function(V, target) {
                V <- sort(V)
                mincombs <- min(which(cumsum(V) > target))
                Combs <- combn(V, mincombs)
                ans <- mapply(function(x,y) ifelse(y > 0, paste0(paste0(Combs[1:y,x], collapse="+"), "=", target), NA), 1:ncol(Combs), apply(Combs, 2, function(I) which(cumsum(I) == target)))
                ans <- unlist(ans[lengths(ans) > 0])
                return(ans)
         }

myfun(V = c(3,9,8,4,5,7,10), target = 15)
myfun(V = c(3,9,8,4,5,7,10,12,4,32),target = 20)

Upvotes: 1

Mark
Mark

Reputation: 4537

Here's a recursive implementation in R

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}

I had to add one extra catch in R from python to handle when i+1 > length(numbers) and returned an NA.

> subset_sum(c(3,9,8,4,5,7,10),15)
[1] "sum(3+8+4)=15"
[1] "sum(3+5+7)=15"
[1] "sum(8+7)=15"
[1] "sum(5+10)=15"

I think (but I'm not sure) that your issue was nest if/else if logic in a recursive function. Interestingly, when I put the if(i+1 > length(numbers)) return() inside the for loop, that broke the functionality so I didn't get all the answers right - the return's need to be outside the recursion.

Upvotes: 1

Related Questions