What's the smallest difference of any (2) numbers that can be formed by using each digit once 0-9?
<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>