suppose I have a integer n
and k
, I need find all the possible combinations of k
integers which sum to n
. I was wondering to how do I implement this efficiently.
right now, what I am doing is super slow, I created kth
cartesian product of a sequence from 1 to n. And then loop over all the possible combinations to check if it satisfy the sum.Below is my code.
first get k cartesian product
cart = function(v,k){
x = v
f = v
for(i in 1:(k-1)){
f = merge(f,x,all=T)
f = as.matrix(f)
colnames(f) = NULL
}
return(f)
}
v is the sequence from 1 to n and k is the integer
then loop over
combine = cart(v=seq(1,n),k=k)
sum = 0
for(i in 1:dim(combine)[1]){
if(sum(combine[i,])==n){
sum = sum + sum(combine[i,])
}
}
this is super slow and I was wondering is there any faster way to implement this?
See Question&Answers more detail:os