See how many ways you can make 1000 using the numbers below i.e 754+246
Easy eh? NOPE!
59, 123, 156, 246, 274
329, 338, 465, 487, 512
573, 619, 692, 754, 781
853, 871, 945, 924, 382
I got one!
Printable View
See how many ways you can make 1000 using the numbers below i.e 754+246
Easy eh? NOPE!
59, 123, 156, 246, 274
329, 338, 465, 487, 512
573, 619, 692, 754, 781
853, 871, 945, 924, 382
I got one!
only two ways
59,274,329,338
and of course 754,246
simple if using visual studio c# and a console app :)
oh and I was lazy and I googled the code below, given time I would have done it from scratch, buy hey ho, 2 mins and job done,
Code:private static void Main(string[] args) {
int[] set =
{
59, 123, 156, 246, 274, 329, 338, 465, 487, 512, 573, 619, 692, 754, 781, 853, 871, 945, 924,
382
};
foreach (string s in GetCombinations(set, 1000, ""))
{
Console.WriteLine(s);
}
Console.ReadKey();
}
public static IEnumerable<string> GetCombinations(int[] set, int sum, string values)
{
for (int i = 0; i < set.Length; i++)
{
int left = sum - set[i];
string vals = set[i] + "," + values;
if (left == 0)
{
yield return vals;
}
else
{
int[] possible = set.Take(i).Where(n => n <= sum).ToArray();
if (possible.Length > 0)
{
foreach (string s in GetCombinations(possible, left, vals))
{
yield return s;
}
}
}
}
}
but then again question is not very clear, is that just addition, or can we use division, multiplcation, substraction etc
if so then code gets complicated
anyway, its late, night night
As its an 8 year olds homework I would assume its just adding and subtracting?
Thanks for your replies, much appreciated.
This is a stupid exercise and as a parent I'd give feedback on that, it's not teaching the kid anything other than trial and error and unless I'm wrong the solution is what's called np complete and there's a million dollar prize if you can prove it can be solved otherwise (other than trying every permutation - which with this I guess you don't)
actually this is quite a good interview question in some ways for coders. Might steal it. If you sort the list you obviously can't have two above the mid point so reduces choices - you can then work through the list like some of the sorting algorithms (which if you're at all interested there's visual video/graphics of how they work on wikipedia).
anyway - Id say that's a little beyond an 8 year old and something I'd pitch to an experienced coder.