Leo
BAN USERAssume generate m random intgers from n intgers, it can shuffle the first m elements.
int Random(int start, int end)
{
// return a random intger btw start and end;
}
void gr(int m, int n)
{
int *a = new int[n];
for(int i = 0, i < n; i++)
a[i] = i;
for(int i = 0; i < m; i++)
{
int r = Random(i, n-1);
swap(a[i], a[r]);
}
// Output the first m elements of a
}
a bottomup solution:
int f(int *a, int n, int tar)
{
if(n <= 0)
return 0;
map<int, int> m;
m[a[0]] = 1;
m[-a[0]] = 1;
m[0] = 1;
for(int i = 1; i < n; i++)
{
map<int, int> t = m;
m.clear();
for(map<int, int>::iterator it = t.begin(); it != t.end(); it++)
{
m[it->first] += it->second;
m[it->first + a[i]] += it->second;
m[it->first - a[i]] += it->second;
}
}
return m[tar];
}
The complexity of DashDash's solution is O(nlog(k)), Jack's complexity is O(nk). Is there solution with complexity O(n)?
- Leo March 19, 2013