fork(1) download 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Test
  6. {
  7. 	public static void Main()
  8. 	{
  9. 	    var numbers = new[] { 3, 4, 1, 6, 5, 4, 12, 13, 7, 8 };
  10. 	    var target = 9;
  11.  
  12. 	    var problem = new DynamicSubsetSum(numbers, target);
  13.  
  14. 	    foreach (var solution in problem.Solve()) {
  15. 	        Console.WriteLine("Solution: {0}", string.Join(", ", solution));
  16. 	    }
  17. 	}
  18. }
  19.  
  20. class DynamicSubsetSum
  21. {
  22.     private readonly int[] choices;
  23.  
  24.     private readonly int targetSum;
  25.  
  26.     private readonly Dictionary<int, HashSet<int>> partialSolutions = new Dictionary<int, HashSet<int>>();
  27.  
  28.     public DynamicSubsetSum(int[] choices, int targetSum)
  29.     {
  30.         this.choices = choices;
  31.         this.targetSum = targetSum;
  32.     }
  33.  
  34.     public IEnumerable<IEnumerable<int>> Solve()
  35.     {
  36.         this.partialSolutions.Clear();        
  37.         this.SolvePartial(new List<int>(this.choices), this.targetSum);
  38.  
  39.         return !this.partialSolutions.ContainsKey(this.targetSum)
  40.             ? Enumerable.Empty<IEnumerable<int>>()
  41.             : this.ExpandSolutions(this.choices, this.targetSum)
  42.                 .Select(c => c.OrderBy(n => n))
  43.                 .Distinct(new SequenceEquivalenceComparer<int>());
  44.     }
  45.  
  46.     private bool SolvePartial(IEnumerable<int> partialSet, int target)
  47.     {
  48.         if (target == 0) {
  49.             return true;
  50.         }
  51.  
  52.         foreach (var n in partialSet.Where(i => i <= target)) {
  53.             if (this.SolvePartial(partialSet.ExceptFirst(n), target - n)) {
  54.                 this.MarkSolutionFound(target, n);
  55.             }
  56.         }
  57.  
  58.         return this.partialSolutions.ContainsKey(target);
  59.     }
  60.  
  61.     private void MarkSolutionFound(int target, int selection)
  62.     {
  63.         if (!this.partialSolutions.ContainsKey(target)) {
  64.             this.partialSolutions[target] = new HashSet<int>();
  65.         }
  66.  
  67.         this.partialSolutions[target].Add(selection);
  68.     }
  69.  
  70.     private IEnumerable<IEnumerable<int>> ExpandSolutions(IEnumerable<int> partialSet, int number)
  71.     {
  72.         if (number == 0) {
  73.             return Enumerable.Repeat(Enumerable.Empty<int>(), 1);
  74.         }
  75.         else {
  76.             return this.partialSolutions[number]
  77.                 .IntersectionWith(partialSet)
  78.                 .SelectMany(i => this.ExpandSolutions(partialSet.ExceptFirst(i), number - i).Select(s => s.Concat(new[] { i })));
  79.         }
  80.     }
  81. }
  82.  
  83. class SequenceEquivalenceComparer<T> : EqualityComparer<IEnumerable<T>>
  84. {
  85.     public override bool Equals(IEnumerable<T> lhs, IEnumerable<T> rhs)
  86.     {
  87.         return lhs.OrderBy(x => x).SequenceEqual(rhs.OrderBy(y => y));
  88.     }
  89.  
  90.     public override int GetHashCode(IEnumerable<T> collection)
  91.     {
  92.         return 0;
  93.     }
  94. }
  95.  
  96. static class HelperExtensions
  97. {
  98.     public static HashSet<T> IntersectionWith<T>(this HashSet<T> set, IEnumerable<T> collection)
  99.     {
  100.         var copy = new HashSet<T>(set);
  101.         copy.IntersectWith(collection);
  102.  
  103.         return copy;
  104.     }
  105.  
  106.     public static IEnumerable<T> ExceptFirst<T>(this IEnumerable<T> collection, T itemToRemove)
  107.     {
  108.         bool found = false;
  109.         foreach (var item in collection) {
  110.             if (!found && item.Equals(itemToRemove)) {
  111.                 found = true;
  112.                 continue;
  113.             }
  114.  
  115.             yield return item;
  116.         }
  117.     }
  118. }
  119.  
Success #stdin #stdout 0.09s 24416KB
comments (?)
stdin 
Standard input is empty
stdout 
Solution: 1, 3, 5
Solution: 3, 6
Solution: 4, 5
Solution: 1, 4, 4
Solution: 1, 8
https://ideone.com/3o8hM5
language:
C# (gmcs 5.20.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!