QuickSums(recurssive brute no memorisation)

Problem Statement    Problem Statement for QuickSums Problem Statement      Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result. Write a class QuickSums that contains the method minSums, which takes a String numbers and an int sum. The method should calculate and return the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, return -1.   Definition      Class: QuickSums Method: minSums Parameters: String, int Returns: int Method signature: int minSums(String numbers, int sum) (be sure your method is public)        Constraints - numbers will contain between 1 and 10 characters, inclusive. - Each character in numbers will be a digit. - sum will be between 0 and 100, inclusive.   Examples 0)      "99999" 45 Returns: 4 In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions. 1)      "1110" 3 Returns: 3 Be careful with zeros. 1+1+1+0=3 and requires 3 additions. 2)      "0123456789" 45 Returns: 8 3)      "99999" 100 Returns: -1 4)      "382834" 100 Returns: 2 There are 3 ways to get 100. They are 38+28+34, 3+8+2+83+4 and 3+82+8+3+4. The minimum required is 2. 5)      "9230560001" 71 Returns: 4 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:        Single Round Match 197 Round 1 - Division II, Level Three

------------------------------------editorial---------------------------------------------------------------------

constrains is too low soo need  not to memorise in dp state 

#include<bits/stdc++.h>

using namespace std;

int dp[1000][1000];

int mini=10000;

int solve(string s, int sum_r,int index,int cut,int last_val)

 {

  if(sum_r==0 && index>=s.length()  && last_val==0)

   {

     mini=min(mini,cut);

     return 0;

  }

  else if(index==s.length())

   {

     if(sum_r-last_val==0)

      {

       mini=min(mini,cut);

       return 0;

 }

   }

  else if(sum_r<0 || index>=s.length()) return 0;

  

  else

  {

    last_val=last_val*10+s[index]-'0';

     solve(s,sum_r-last_val,index+1,cut+1,0);

      if(last_val<=1000)

     solve(s,sum_r,index+1,cut,last_val);

      

  }

 

 }

int minSums (string num, int sum) 

{

      solve(num,sum,0,0,0);

      if(mini!=10000)

       cout<<mini<<endl;

       else cout<<-1<<endl;

  

}

int main()

 {

  string s;

  int sum;

   cin>>s>>sum;

  minSums(s,sum);

 }