0

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
Corel
  • 581
  • 3
  • 21
  • I'm probably misunderstanding, but how can you have the function `subset_sum` being used in your function, also called `subset_sum`? – Quinn Sep 20 '17 at 15:27
  • 2
    @Visser: it's called **recursion**, which is one of the tags on the question. It's an interesting topic; do a little research and have fun. – Prune Sep 20 '17 at 15:39
  • 2
    Try `remaining <- numbers[(i+1):length(numbers)]`. Be careful with operator precedence with `:` and `+` – MrFlick Sep 20 '17 at 16:26
  • @MrFlick: Thanks! As it seems this was my problem. – Corel Sep 21 '17 at 09:27

2 Answers2

1

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)
CPak
  • 13,260
  • 3
  • 30
  • 48
1

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.

Mark
  • 4,387
  • 2
  • 28
  • 48
  • Thanks, I used the `sprintf()` method instead of `cat` as this is more convenient. But really my problem was (I'm a little embarrassed) the parenthesis around `i+1` within the assignment to `remaining` in the recursion. – Corel Sep 21 '17 at 09:30
  • @Corel if my answer is correct, I'd love you flagging it as such! – Mark Sep 21 '17 at 14:08
  • Your answer is not wrong, but the answer by MrFlick in the comments section above really gave me the problem that my code was having – Corel Sep 22 '17 at 10:47