title: What's the smallest difference of any (2) numbers that can be formed by using each digit once 0-9?
body: <p>Suppose you have <strong>digits</strong> = <code>{0,..,9}</code>.</p>
  
  <p>Suppose you have an <strong>input</strong> which is a subset of <strong>digits</strong> with cardinality of at least <code>2</code>.</p>
  
  <p>Consider all possible base 10 integers pairs <strong>a</strong> and <strong>b</strong> such that each element in <strong>input</strong> is used once in either <strong>a</strong> or <strong>b</strong> and with no leading <code>0</code>'s (an actual value of <code>0</code> is okay, though).</p>
  
  <p>The <code>Solve</code> algorithm is find the minimum of the absolute value of the difference of all valid pairs from the input.</p>
  
  <p>For example, if <strong>input</strong> = <code>{ 0, 1, 2, 4, 6, 7 }</code>.</p>
  
  <p>There are lots of possible pairs that use each digit exactly once, for example <strong>a</strong> = <code>210</code> and <strong>b</strong> = <code>764</code> and <strong>a</strong> = <code>204</code> and <strong>b</strong> = <code>176</code>.</p>
  
  <p>As it turns out the second pair has the minimum absolute value difference (<code>28</code>).</p>
  
  <p><strong>input</strong> will be provided to a <code>static</code> method called <code>Solve</code> as a string with each digit separated by a single space in ascending order.  You can assume that the input is valid and sorted.</p>
  
  <p><strong>Question: What correct C# implementation of <code>Solve</code> has the best runtime (without just pre-computing/hardcoding each of the <code>~2^10</code> solutions individually)?</strong></p>
  
  <p>Here's what I've tried so far and it seemed to work with the sample input (I did what was most intuitive and readable. I also broke it up into several methods with the hope each could be "unit" tested relatively easily to troubleshoot in case it didn't just "work" the first time.):</p>
  
  <pre><code>class Program
  {
      static void Main(string[] args)
      {
          var input = "0 1 2 4 6 7";
          var result = Solve(input);
      }
  
      private static int Solve(string input)
      {
          var digits = input.Split(' ').Select(i =&gt; int.Parse(i)).ToArray();
          return GetSmallestDifference(digits) ?? -1;
      }
  
      public static int? GetSmallestDifference(IEnumerable&lt;int&gt; input)
      {
          var validInput = ValidateInput(input);
  
          var candidates = GenerateCandidates(validInput);
  
          int? best = null;
          foreach (var candidate in candidates)
          {
              var current = Math.Abs(candidate.Item1 - candidate.Item2);
              if (current &lt; (best ?? int.MaxValue))
              {
                  best = current;
              }
          }
          return best;
      }
  
      private static IEnumerable&lt;Tuple&lt;int, int&gt;&gt; GenerateCandidates(int[] validInput)
      {
          var found = new HashSet&lt;string&gt;();
  
          var nonZeroDigits = validInput.Except(new[] { 0 });
          var max = int.Parse(string.Join("", nonZeroDigits.OrderByDescending(i =&gt; i)));
          for (int i = 0; i &lt;= max; i++)
          {
              var potential = i;
              var complements = GetComplements(potential, validInput);
              if (complements != null)
              {
                  foreach (var complement in complements)
                  {
                      var signature = GetSignature(potential, complement);
                      if (!found.Contains(signature))
                      {
                          found.Add(signature);
  
                          yield return Tuple.Create(potential, complement);
                      }
                  }
              }
          }
      }
  
      private static string GetSignature(int potential, int complement)
      {
          // Sort it so we don't get duplicates.
          var key = new[] { potential, complement }.OrderBy(i =&gt; i).ToArray();
          var formatted = string.Format("{0} {1}", key[0], key[1]);
          return formatted;
      }
  
      private static List&lt;int&gt; GetComplements(int potential, int[] validInput)
      {
          var remaining = validInput.ToList();
          var digits = potential.ToString().Select(c =&gt; int.Parse(c.ToString())).ToArray();
  
          foreach (var d in digits)
          {
              // This means the potential isn't a valid candidate.
              if (!remaining.Contains(d))
              {
                  return null;
              }
  
              remaining.Remove(d);
          }
  
          // This means there were no other digits to choose.
          if (remaining.Count == 0)
          {
              return null;
          }
          else
          {
              var complements = new List&lt;int&gt;();
              Scramble(complements, "", remaining);
              return complements;
          }
      }
  
      private static void Scramble(List&lt;int&gt; complements, string result, IEnumerable&lt;int&gt; remaining)
      {
          if (remaining.Any())
          {
              foreach (var i in remaining)
              {
                  var childResult = result + i;
                  var childRemaining = remaining.Except(new[] { i });
  
                  Scramble(complements, childResult, childRemaining);
              }
          }
          else
          {
              if (!result.StartsWith("0") || result.Length == 1)
              {
                  var intResult = int.Parse(result);
                  complements.Add(intResult);
              }
          }
      }
  
      private static int[] ValidateInput(IEnumerable&lt;int&gt; input)
      {
          // Make sure (2) integers were entered.
          if (input == null || input.Count() &lt; 2)
          {
              // TODO
              throw new Exception();
          }
  
          // Make sure you don't have duplicates.
          var result = input.Distinct().ToArray();
  
          // Make sure the numbers are in range.
          if (result.Min() &lt; 0 || result.Max() &gt; 9)
          {
              // TODO
              throw new Exception();
          }
  
          return result;
      }
  }
  </code></pre>
  
  <p><em>(This question was recently asked by another user but appears to have been deleted by the user; I already came up with an answer, though, so I didn't want SO to lose it.  I re-worded and re-formatted the question, slightly.)</em></p>