find subset sum from value list

[osman3144]

hi friends,

ı have a question is there anyone to help me?

ı have 2 list below; targetValueList and ValueList.

targetValueList <- c(100378,20887,14367,11977,10822,8888,7932,6899,6842,6121,5830,5295,5138,4461,2498,899,879,549,254,188,13)

ValueList<- c(-11,-149,-167,-188,-227,-254,-400,-672,-1641,-1864,-4461,-4637,-4843,-5830,-6121,-6844,-10820,-11977,-14367,-21082,-24195,-100367)

ı am trying to find which combination of negative numbers from my negative list sums up to any positive number from the first list .

for example (-100367 and -11)*-1 is equal to 100378

how can ı solve this problem.

ı got stuck here.

[williaml]

I'm sure that someone will be able to come up with something better than this. But through sampling numbers from the lists will get you some of the answers.

targetValueList <- c(100378,20887,14367,11977,10822,8888,7932,6899,6842,6121,5830,5295,5138,4461,2498,899,879,549,254,188,13)
ValueList<- c(-11,-149,-167,-188,-227,-254,-400,-672,-1641,-1864,-4461,-4637,-4843,-5830,-6121,-6844,-10820,-11977,-14367,-21082,-24195,-100367)


set.seed(1)
library(purrr)
random_lists <- map(1:10000, ~tibble(nums = sample(ValueList, sample(2:length(ValueList)))))
sum_of_random_lists <- map_vec(random_lists, ~sum(.x$nums))
pos_sum_random_lists <- sum_of_random_lists * -1
values_that_match_pos <- pos_sum_random_lists[which(pos_sum_random_lists %in% targetValueList)]
position_of_matching <- match(unique(-values_that_match_pos), # as negative values
                              sum_of_random_lists)  
  
random_lists[position_of_matching]

Output:

[[1]]
# A tibble: 2 x 1
   nums
  <dbl>
1  -400
2  -149

[[2]]
# A tibble: 3 x 1
   nums
  <dbl>
1  -149
2 -5830
3 -4843

[[3]]
# A tibble: 2 x 1
     nums
    <dbl>
1 -100367
2     -11

[[4]]
# A tibble: 3 x 1
   nums
  <dbl>
1 -6844
2  -672
3 -4461

[[5]]
# A tibble: 2 x 1
   nums
  <dbl>
1  -227
2  -672

[AlexisW]

Is a "combination" always an addition, or can it be multiplication, subtraction, division?
Is it always a combination of 2 elements, or can it be more (or less)?
Do you need at least one combination, all possible combinations, ... ? Or maybe you're guaranteed to have exactly one combination per target?
Are you getting arbitrary lists that can be much longer than this (typical for problems from sites like CodeWars, Project Euclid, Exercism etc), or is this just this one list?

An approach could be to loop on target values, and for each one try to find all combinations. Depending on the answers to the questions above, maybe you can just use combn(), maybe you need some "tricks", for example you could pre-filter numbers that are bigger than the target. Williaml's approach seems good if you don't need every possible combination.

[osman3144]

@AlexisW

always an addition, or can it be multip

for example,
as combination ı mean addition like -8888 is combination of ( -149)+( -167)+ (-188)+( -227)+( -254)+( -400)+( -672)+( -6844)

[AlexisW]

Then yeah, as a first pass I would go with combn() to get every possible combination (varying the number of elements), and rowSums() or colSums() to get the sums, then check if they're %in% the targets.

Chances are this approach will become infeasible if the input vector is too big (too many combinations), and you'll need to refine it.