Finding sum of number combination from number string in C

Question

i need help with one problem in C. I have two numbers. First is "number string" (i represent it in string), i need to split it to any combination of numbers those sum of them give me second number. For example : 888 24 I need to split it into 8 + 8 + 8 The returned number is count of + elements. In example is answer 2. Split it into every one digit is easy but i dont know how to do it in different cases.

1234 46  (12+34)
1234 127 (123+4)
101 2    (1+01)

When i dont find any combination returned value is IMPOSSIBLE.

i have this to split string into numbers but i dont know how apply it successfully :/

long** printComb(char *line, int l, int lp, int r, int rp){

char **vys;
  vys = (char**) malloc(2*sizeof(char*));
  vys[0] = (char*) malloc(lp*sizeof(char));
  vys[1] = (char*) malloc(rp*sizeof(char));
  int i;

  for(i = 0; i < lp; i++)
    vys[0][i] = line[l+i];
  vys[0][i] = '\0';

  for(i = 0; i < rp; i++)
    vys[1][i] = line[r+i];
   vys[1][i] = '\0';


  return vys;
}

Thanks for every advice :)

Welcome to Stack Overflow! [Please see this discussion on why not to cast the return value of `malloc()` and family in `C`.](http://stackoverflow.com/q/605845/2173917). — Sourav Ghosh, Mar 08 '16 at 21:03
Note that you malloc a lp sized block, then use that pointer to fill lp+1 values. — Steve Kolokowsky, Mar 08 '16 at 22:07
You return vys, which is a `char **`, but have a return type of `long **` in the function signature: **not good** — Daniel Jour, Mar 08 '16 at 23:07

score 0 · Accepted Answer · edited May 23 '17 at 12:23

This a combination problem. The brutal force way to go would be combining all possible values and then filter the ones that have reached the value you want. For example:

123: (123); (1, 23); (12, 3); (1, 2, 3);

Supposing we want to find a sum that gives 15, the answer would be (12, 3). Another example could be:

1234: (1234); (1, 234); (12, 34); (123, 4); (1, 2, 34); (1, 23, 4); (12, 3, 4); (1, 2, 3, 4);

And, as you said, if we want to find a sum that gives 46, the answer would be (12, 34).

A set of solutions in other languages such as Python can be found at Finding all possible combinations of numbers to reach a given sum. Also, if you have any difficulty implementing this in C take a look at http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ and then extend the idea to combine from 1 to N elements, where N is the size of the string.

Finding sum of number combination from number string in C

1 Answers1