39. Combination sum

39. Combination sum - a year ago, two year ago two submissions. 

I wrote a post to share on June 22, 2019 based on practice in 2018. Here is the link.

It is time for me to review backtracking algorithm on June 22, 2019. Here is the article I like to review written by a Google engineer. I like to review all algorithms in the article, and I like to share my practice in 2018.

Most important is to avoid timeout issue, one way is to avoid copy the list for each depth first search. If backtracking is used, then only one list is needed for all the searches. Shared space is more efficient, and easy to backtracking as well.

Case study to understand backtracking
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

First, sort the array with all numbers, [2, 3, 6, 7], no duplicate.
Base case, target = 0, empty set.

Remember that we only allow to use one list to store all numbers selected for the target; We will maintain the order of numbers using data structure List, and also add last and pop last for backtracking as well.

Let us start from index = 0, first number is 2, and then 2 is added to the list, continue to search, DFS next step, target is 7 - 2= 5, what is start index for next step?

Work on next index in the design
start index should be index + 1= 1, or index? This is most challenging problem.
One of answers is [2, 2, 7], in other words, next element should start from all possible numbers not less than current number. 2 can be selected more than once consecutively.

In other words, next step is to search from index = 0 again for target = 5, choose 2, put 2 into list, so the list is [2, 2], target = 3, then search next step, [2, 2, 2], target = 1, we could not find any number less than 1, so backtrack, pop last 2 out from list, and then search next step index = 1, value = 3, [2, 2, 3], base case target = 3 is meet, the list is added to final result.

Step by step DFS

[2,2,3], target 7
Base case:
{} empty set -> empty list
List
[2, 3, 6, 7]
Four options to start with, first one is 2,
start with 2,
[2] -> target 5, index start = 0, next step start index still 0
[2, 2] -> target 3, index start = 0,
[2, 2, 2] -> target 1, index start = 0, value: 2 > target: 1, backtrack
[2,2, 3], try next target 0, find the first combination.

[2, 3] -> target 2, index start = 1,
[2, 3, 3] -> value > 8, backtrack

...

My idea of reviewing the solution is to go over the basic DFS steps, and I can explain it clearly like mock interview. The code should be easily to be reviewed.

The above step by step explanation will be reviewed and make it more readable and clearly. I will think about drawing some diagram to help if need.

C# API - how to remove List last item
Here is the idea by looking up stackoverflow.com
List.RemoveAt(rows.Count - 1)

Here are highlights:

1. Apply depth first search; sort the array in ascending order to help avoid duplicate constraint, since [2, 2, 3] should be same as [2, 3, 2], the order is not important;
2. Understand that one number can be used multiple times in the combination, so DFS next step start index should be the same as the current one, therefore same number can be selected more than once.
3. Backtracking is important technique, it is DFS, so the list will be expanded to meet the target or bigger than target or exhaust all possible numbers, and then backtrack, pop last one to allow all options are exhausted.

Time complexity analysis

Each DFS step search at most have n options, n is size of the array. So at most there are target (T) steps in DFS search, so time complexity is O(n^T).

At the beginning, if I decide to analyze time complexity, then I will have a good idea how to solve the problem.

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            var result = new List<IList<int>>();
            var combination = new List<int>();
            Array.Sort(candidates);

            CombinationSum(result, candidates, combination, target, 0);
            return result;
        }

        /// <summary>
        /// I like to talk about the design:
        /// this algorithm is like brute force solution, using back tracking. 
        /// combination can be bruted force to find solution. Like minimum value in the combination. 
        /// starting from each one. 
        /// </summary>
        /// <param name="result"></param>
        /// <param name="candidates"></param>
        /// <param name="combination"></param>
        /// <param name="target"></param>
        /// <param name="start"></param>
        private static void CombinationSum(
            IList<IList<int>> result, 
            int[] candidates, 
            IList<int> combination, 
            int target, 
            int start)
        {
            if (target == 0)
            {
                result.Add(new List<int>(combination));
                return;
            }

            // enforce the combination numbers in the list will be non-descending order
            // brute force the start value from all possible values starting from start variable
            for (int i = start; i != candidates.Length && target >= candidates[i]; ++i)
            {
                combination.Add(candidates[i]);
                CombinationSum(result, candidates, combination, target - candidates[i], i);
                combination.Remove(combination.Last());
            }
        }
}