This can be reduced to the standard subset sub problem. For algorithms
to solve it consider reading about it here,
http://en.wikipedia.org/wiki/Subset_sum_problem
This is my implementation for solving this problem provided the range
of values that the array can take is small(from 0 to MXSUM-1
inclusive).
#include <cstdio>
#include <cstring>
using namespace std;
#define REP(i, n) for(int i = 0, _n(n); i <(_n); i++)
typedef long long LL;
const int MXCNT = 111, MXSUM = 111111;
int a[MXCNT], mk[MXSUM], subsets[MXSUM];
int main() {
int n, k;
scanf("%d%d", &n, &k);
REP(i, n) scanf("%d", &a[i]);
memset(mk, 0, sizeof(mk));
memset(subsets, 0, sizeof(subsets));
int cnt = 0;
subsets[cnt++] = 0;
int ok = 0;
REP(i, n) {
REP(j, cnt) {
int tmp = subsets[j]+a[i];
if(!mk[tmp]) {
if(tmp==k) ok = 1;
subsets[cnt++] = tmp;
mk[tmp] = 1;
}
}
}
printf("%d\n", ok);
}
On Jul 30, 9:36 pm, Dumanshu <duman...@gmail.com> wrote:
> Given an array of length n of integer numbers. Output 1 or 0 depending
> on whether or not there exists a sub sequence in the array with sum S.
> Suggest a fastest algorithm plz.
>
> e.g. say given an array with numbers as 10 20 30 40 50 60 70
> Sum = 110
>
> Output is 1 because 20+30+50 is 110.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
