Leetcode discuss: 39. Combination Sum

March 17, 2022

Here is the link. 

C# | Warmup practice | DFS | Backtracking | 2022

March 16, 2022
Introduction
It takes me 10 minutes to review C# code, and I wrote my own practice. The challenge part is to learn that if the array is sorted first, later it can easily terminate the search by checking target value; backtracking is standard to call C# List.RemoveAt, and then same number in the array can be allowed to be added more than once, I added comment to remind myself.

Review subset (Combination and permutation)
Leetcode 90, 78, 77, 39 ( combination sum) - Book chapter - Li Yin

DFS Backtracking Analysis
This is still a typical combination problem, the only thing is the return level is when the sum of the path we gained is larger than the target, and we only collect the answer when it is equal. And Because a number can be used unlimited times, so that each time after we used one number, we do not increase the next start position.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _39_Combination_Sum
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var result = test.CombinationSum(new int[]{2, 3, 6, 7}, 7);
            var list = string.Join(",",result[0]);
            Debug.Assert(list.CompareTo("2,2,3") == 0 || list.CompareTo("7") == 0);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/combination-sum/discuss/16669/C-backtracking-implementation
        /// </summary>
        /// <param name="candidates"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        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>
        /// depth first search, backtracking 
        /// all combination - same number can be used more than once
        /// input array: candidates - distinct, value is between 1 and 200
        /// </summary>
        /// <param name="result"></param>
        /// <param name="candidates"></param>
        /// <param name="combination"></param>
        /// <param name="target"></param>
        /// <param name="start"></param>
        private 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;
            }

            // sorting makes easy to prune the algorithm, terminate the search by checking target value
            for (int i = start; i != candidates.Length && target >= candidates[i]; ++i)
            {
                var current = candidates[i];

                combination.Add(current);

                // variable: start - i, not i + 1, so number can be added more than once
                CombinationSum(result, candidates, combination, target - current, i); 
                combination.RemoveAt(combination.Count - 1);
            }
        }
    }
}