Guest User

UnlimitedCoinsSum

a guest
Oct 21st, 2015
25
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. namespace CoinsSum
  2. {
  3.     using System;
  4.     using System.Linq;
  5.  
  6.     public class CoinsSum
  7.     {
  8.         public static void Main()
  9.         {
  10.             Console.WriteLine("Enter target sum:");
  11.             var targetSum = int.Parse(Console.ReadLine());
  12.             Console.WriteLine("Enter numbers separated with \",\"");
  13.             var nums = Console.ReadLine().Split(new string[] { "," }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
  14.  
  15.             var ways = GetSumWays(nums, targetSum);
  16.  
  17.             Console.WriteLine("Total combinations: " + ways.Length);
  18.  
  19.             // Uncomment to print possible combinations
  20.             //foreach (var way in ways)
  21.             //{
  22.             //    Console.WriteLine(string.Join(" ", way));
  23.             //}
  24.         }
  25.  
  26.         public static int[][] GetSumWays(int[] array, int k)
  27.         {
  28.             int[][][] ways = new int[k + 1][][];
  29.             ways[0] = new[] { new int[0] };
  30.  
  31.             for (int i = 1; i <= k; i++)
  32.             {
  33.                 ways[i] = (
  34.                     from val in array
  35.                     where i - val >= 0
  36.                     from subway in ways[i - val]
  37.                     where subway.Length == 0 || subway[0] >= val
  38.                     select Enumerable.Repeat(val, 1)
  39.                         .Concat(subway)
  40.                         .ToArray()
  41.                 ).ToArray();
  42.             }
  43.  
  44.             return ways[k];
  45.         }
  46.     }
  47. }
RAW Paste Data