1: namespace Recursion1
2: { 3: /// <summary>
4: /// Question:
5: /// For a list of integers (positive and negative) check if there's
6: /// a combination within them that when you will sum them the result will be a specific amout.
7: /// Use the following signature: bool IsCover(int[] values, int amount) and solve in recursion.
8: /// </summary>
9: class Program
10: { 11: /// <summary>
12: /// Test the solution
13: /// </summary>
14: /// <param name="args"></param>
15: static void Main(string[] args)
16: { 17: int[] values = new int[] { 5, 22, 13, 5, 7, -4 }; 18: Console.WriteLine("List: "); 19: values.ToList().ForEach(
20: (val)=>
21: { 22: Console.Write(val);
23: Console.Write(" "); 24: });
25: Console.WriteLine();
26:
27: new int[]{42,31,-5,17,13,23}.ToList().ForEach( 28: (amount)=>
29: { 30: Console.WriteLine("Can cover amount {0} = {1}", amount, IsCover(values, amount)); 31: });
32:
33: Console.ReadLine();
34: }
35:
36: /// <summary>
37: /// Solution
38: /// </summary>
39: /// <param name="values">list of numbers</param>
40: /// <param name="amount">amount to cover by the values</param>
41: /// <returns>if can be covered or not</returns>
42: public static bool IsCover(int[] values, int amount)
43: { 44: if (values==null || values.Length==0)
45: return amount == 0;
46:
47: //bootstrap
48: return IsCover(values, 0, amount);
49: }
50:
51: /// <summary>
52: /// Bootstraped method
53: /// </summary>
54: /// <param name="values"></param>
55: /// <param name="i">starting index</param>
56: /// <param name="amount"></param>
57: /// <returns></returns>
58: private static bool IsCover(int[] values, int i, int amount)
59: { 60: if (i >= values.Length)
61: return amount == 0;
62:
63: return
64: IsCover(values, i + 1, amount - values[i]) //try to cover using value from index i
65: || IsCover(values, i + 1, amount); //try to cover without using the value in index i
66: }
67: }
68: }