algorithm - Represent a number as a sum of a subset of an array -

given natural number s>10, generate array of n natural numbers = (a1, a2, …, ak, …, an) such s sum of m ai.

constraint 1:

ai < s/2 

constraint 2:

m >= k 

constraint 3 (optional): ai != aj

sorry, i’m not sure how describe problem using proper mathematical notation, idea simple: generate values add pre-defined total. , add more values (“decoys” were) make task of selecting right values use more difficult.

let's s=18 , want represented sum of @ least 3 values. so, "winning" array a=(7,8,3,4,5) because 7+8+3=18 , there's no way use less 3 values 18.

i have simple algorithm kinda works:

input:  s - sum k - number of values required add s n - total number of values (includes decoys)  output:  - array of values ai  1) generate k values dividing s k , adding , subtracting random numbers. ensures ai more or less random while still adding s.  2) generate (n-k) random values less s/2 each.  3) combine generated values 1 array a.  4) test s can represented sum of no less k values array a. if not, discard , return 1)  example: s = 20 k = 3 n = 5 ai values generated: 7, 1, 12, 4, 8, 7+1+12=20 – need (3 values add 20)  can 20 2 values , violates constraint 2: 12+8 = 20 

of course, brute-force approach , check many iterations, it's not right way it.

my question: possible generate array automatically meet constraint 1,2,3 or @ least constraints 1,2?

for positive integers, short answer no: counterexample s=1 k=2. however, avoiding obvious,

createlonglist(s,k) {   list= {};   for(i=1 s/2)     if(canadd(list,s,k,i))       list.add(i);     else break; } 

will create maximum size list? maybe not, pretty well. without getting math, recursive search give guaranteed best result.

#list=={} first time, istart=s/2 createlonglist(s,list,k,istart) {   bestlist=list;   for(i=istart 1)      if(canadd(list,s,k,i))        newlist=createlonglist(s,list++i,k,i-1);        if(newlist.islongerthan(bestlist))          bestlist=newlist;   return bestlist; }