Leetcode 39: Combination sum

July 30, 2018

Introduction

It is a medium level algorithm called combination sum. But I felt that it is so hard to come out a solution with well-defined time complexity. All I can think about is brute force solution. I like to sort the candidate numbers and then brute force minimum value in the combination sum.

I have the idea but how to write a workable code. I really think about getting general ideas about the algorithm.

It is time to look into Leetcode discussion related to the algorithm. One of C# solutions is here to study.

My practice

I also like to write C# code this time to learn the algorithm again. I also wrote some analysis in the code, I like to help myself to understand the algorithm better this time.

Here is C# practice code in July 2018.

Here is C# practice code in June 2017.

My goal of research 

I came cross this algorithm last night, and I did spend over 10 minutes to think about the algorithm. I could not believe that I wrote a solution just one year ago. I was nervous, and I thought about a few things. I asked myself what is brute force solution. Let me sort the candidate first. What is the minimum number in combination? Can we brute force on this minimum number? How many steps to take to calculate all possible choice for a combination?

In order for me to get comfortable on the algorithm problem solving, I did look into and answer the question when I practice this time.

	/// <summary>
	/// time complexity analysis:
	/// combination starting from 2, target 7, minimum is 2, at most 4 elements in one combination
	/// starting from 2, look for at most another 3 elements -> recursive function, depth first search
	/// at most 3 time, exhaust all options. Each step at most 4 options. So in total will be 4^3 = 64 recursive
	/// calls.
	/// next step, minimum value in combination starts from 3, each step at most 3 options, so in total
	/// will be 3^3 = 27 calls
	/// so the recursive calls should be 4^3 + 3^3 + 2^3 + 1 ^3
	/// the idea is to sort the candidates first in ascending order.
	/// </summary>
	public static void RunTestcase()
	{
	var result = CombinationSum(new int[]{2,3,6,7}, 7);
	}
	public static 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());
	}
	}

view raw Leetcode39_combinationSum.cs hosted with ❤ by GitHub