Calculating 4 or n Sum in R

Question

I am trying to practice LeetCode problems for Data Scientist interviews in R and One of the question I came across is foursum. To solve this, I am trying to generate all the different four combinations and calculating the sum using apply function. Is there a better way to optimize it in R without using combn?

GetFourSumCombinations <- function(TestVector,Target){
  CombinationPairs = combn(TestVector, 4)  ## Get all the combinations
  SumOfAllCombinations = apply(CombinationPairs, 2, sum)
  TargetElements = which(SumOfAllCombinations == Target)
  return(CombinationPairs[,TargetElements])
}
## OutPut:
TestVector = c(1, 0, -1, 0, -2, 2), Target = 0
GetFourSumCombinations(TestVector,0)
     [,1] [,2] [,3]
[1,]    1    1    0
[2,]    0   -1    0
[3,]   -1   -2   -2
[4,]    0    2    2

`combn()` can take a function to calculate a value for one combination. — jogo, Jun 14 '19 at 13:45
Yes, I understand that but I am supposed to print all the combinations not the `sum` — Jason Mathews, Jun 14 '19 at 13:51
If you are checking for a faster version, check [here](https://stackoverflow.com/questions/26828301/faster-version-of-combn) Lots of alternatives — akrun, Jun 14 '19 at 15:21

score 3 · Answer 1 · answered Jun 14 '19 at 13:45

3

Here is a bit shorter version

GetFourSumCombinations <- function(TestVector,Target){
   vals <- combn(TestVector, 4)
   vals[, colSums(vals) == Target]
}

GetFourSumCombinations(TestVector, Target)

#     [,1] [,2] [,3]
#[1,]    1    1    0
#[2,]    0   -1    0
#[3,]   -1   -2   -2
#[4,]    0    2    2

data

TestVector <- c(1, 0, -1, 0, -2, 2)
Target = 0

answered Jun 14 '19 at 13:45

Ronak Shah

377,200
20
156
213

Well, the main thing is to find an alternative for `combn` and it is computationally expensive. – Jason Mathews Jun 14 '19 at 13:47
1

Brilliant solution! – SteveS Jun 14 '19 at 13:47
@JasonMathews well, an alternative would be to use nested loops over each combination. I am not sure how efficient that would be though. – Ronak Shah Jun 14 '19 at 14:01
Sweet!! Your solution for sure is better version of mine but I believe it is not the optimized one and the knowledge on `data structures` is beyond me. I'll wait for other solutions before I accept your answer. – Jason Mathews Jun 14 '19 at 14:03

G. Grothendieck · Answer 2 · 2019-06-14T15:16:36.247

2

Run combn , convert that to a data.frame and then Filter out the desired columns. This has a one-line body and no subscripting.

target4 <- function(x, target = 0) {
  Filter(function(x) sum(x) == target, as.data.frame(combn(x, 4)))
}

TestVector <- c(1, 0, -1, 0, -2, 2)
target4(TestVector)

giving:

  V1 V9 V14
1  1  1   0
2  0 -1   0
3 -1 -2  -2
4  0  2   2

2) Longer but does not use combn.

target4a <- function(x, target = 0) {
  g <- do.call("expand.grid", rep(list(seq_along(x)), 4))
  ok <- apply(g, 1, function(x) all(diff(x) > 0))
  g2 <- apply(g[ok, ], 1, function(ix) x[ix])
  g2[, colSums(g2) == target]
}

target4a(TestVector)

3) or perhaps break up (2) into a custom combn and (1).

combn4 <- function(x) {
  g <- do.call("expand.grid", rep(list(seq_along(x)), 4))
  ok <- apply(g, 1, function(x) all(diff(x) > 0))
  apply(g[ok, ], 1, function(ix) x[ix])
}

target4b <- function(x, target = 0) {
  Filter(function(x) sum(x) == target, as.data.frame(combn4(x)))
}

target4b(TestVector)

edited Jun 14 '19 at 15:16

answered Jun 14 '19 at 14:24

G. Grothendieck

254,981
17
203
341

Sure , it is a simple version. Wondering if it can be done without using `combn` function. – Jason Mathews Jun 14 '19 at 14:29
OK. Added a second approach. – G. Grothendieck Jun 14 '19 at 14:58
Don't you think `expand.grid` is similar to `combn`? I initially solved this using `expand.grid` and then found out that `combn` is faster than `expand.grid`. – Jason Mathews Jun 14 '19 at 15:06
1

No, I think they are completely different. – G. Grothendieck Jun 14 '19 at 15:13
1

Have added (3). – G. Grothendieck Jun 14 '19 at 15:17
Thanks G. Grothendieck. I'll go with your knowledge. – Jason Mathews Jun 14 '19 at 15:17
wouldn't `expand.grid` create more combinations along with repeated combinations to check than `combn` ? `combn(1:5, 2)` vs `expand.grid(1:5, 1:5)` ? – Ronak Shah Jun 14 '19 at 15:42
Yes, of course, but the poster is asking for solutions not using combn. – G. Grothendieck Jun 14 '19 at 23:51

Calculating 4 or n Sum in R

2 Answers2