Combination Sum 3: one line to rule them all

Leetcode again: https://leetcode.com/problems/combination-sum-ii/, and here is the description:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

I've done this type of problem multiple times over and over, so in my mind this wouldn't take that long. There was one caveat to this problem (the fact that we don't want duplicated lists) which I did not give much attention in the beginning (a hash table would eventually help, I thought). Procedure to solve this kind of problem usually involves:

• Since it is asking for all the solutions, DP won't work (thankfully!)
• It will be a DFS, with tree-pruning optimization
• Hash the solutions, put in a table, look for it before adding the solutions back

That did not work. I ran into timeout issues. The first realization was that I could just sort the initial candidates list and by doing so I could return as soon as I found a solution, or as soon as the current sum was greater than the target. That helped, but again, did not eliminate the timeout.

Here is the one line to solve the problem:

In the main loop, as soon as you realize that it is pointless to continue, get the hell out!!! Line is highlighted below. It was enough to make the cut. Cheers, Marcelo.

    public class Solution
    {
        public IList<IList<int>> CombinationSum2(int[] candidates, int target)
        {
            List<IList<int>> solution = new List<IList<int>>();
            Array.Sort(candidates);

            CombinationSum2Interal(0,
                                   new List<int>(),
                                   0,
                                   candidates,
                                   "",
                                   new Hashtable(),
                                   target,
                                   solution);

            return solution;
        }

        private void CombinationSum2Interal(int index,
                                            List<int> currentList,
                                            int currentSum,
                                            int[] candidates,
                                            string key,
                                            Hashtable htCombUsed,
                                            int target,
                                            List<IList<int>> solution)
        {
            if (currentSum >= target || index >= candidates.Length)
            {
                if (currentSum == target && !htCombUsed.ContainsKey(key))
                {
                    List<int> copy = currentList.ToList<int>();
                    solution.Add(copy);
                    htCombUsed.Add(key, true);
                }
                return;
            }

            for (int i = index; i < candidates.Length; i++)
            {
                currentList.Add(candidates[i]);
                int position = currentList.Count - 1;

                CombinationSum2Interal(i + 1,
                                        currentList,
                                        currentSum + candidates[i],
                                        candidates,
                                        key + candidates[i].ToString() + "@", 
                                        htCombUsed,
                                        target,
                                        solution);

                currentList.RemoveAt(position);

                if (currentSum + candidates[i] >= target) break;
            }
        }
    }