-1

I am working on my school assignment that reads

for a given no. find no. of possible ways to get that no. adding digits from a given set of no.

i.e,

if I am given a set of No. a =1, b=2, c=3, d=4, e=5, f=6 and another no b=7 I need to find the no. of possible ways to get & adding a, b, c, d, e, f. Repetition of digits is allowed. Like in the above case I can get 7 in following ways:

  • 4+3
  • 5+2
  • 4+2+1
  • 6+1
  • 1+1+1+1+1+1+1
  • 2+2+2+1
  • and more

How can I achieve the goal??Their are solutions for the problem in different languages but I don't know any lang except for C, C++;

For Sunny
  • 23
  • 3
  • I am just brute forcing. But, that is taking really long. – For Sunny May 22 '15 at 10:26
  • possible duplicate of [find all subsets that sum to a particular value](http://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value) – VP. May 22 '15 at 10:44
  • No, the solutions to the problem is in C#, Python, Java and I don't know any of these. – For Sunny May 22 '15 at 10:46
  • That C# answer doesn't use any C# features that don't have direct equivalents in C++. Mentally replace `int[]` with `std::vector` and you should be able to understand it. – Ben Voigt May 24 '15 at 00:38

1 Answers1

0

try out this:

#include < iostream>
#include < vector>

using namespace std;

 struct State {
    int v;
    const State *rest;
    void dump() const {
        if(rest) {
            cout << ' ' << v;
            rest->dump();
        } else {
            cout << endl;
        }
    }
    State() : v(0), rest(0) {}
    State(int _v, const State &_rest) : v(_v), rest(&_rest) {}
};

void ss(int *ip, int *end, int target, const State &state) 
{
    if(target < 0) return; // assuming we don't allow any negatives
    if(ip==end && target==0) {
        state.dump();
        return;
    }
    if(ip==end)
        return;
    { // without the first one
        ss(ip+1, end, target, state);
    }
    { // with the first one
        int first = *ip;
        ss(ip+1, end, target-first, State(first, state));
    }
}

int main() {
    int a[] = { 2,59,3,43,5,9,8,62,10,4 };
    int * start = &a[0];
    int * end = start + sizeof(a) / sizeof(a[0]);
    ss(start, end, 12, State());
}
Ankush
  • 132
  • 1
  • 11