416. Partition Equal Subset Sum (backtracking + pruning)

I like to write a solution based on this sharing.

Here is my C# practice usng backtracking and pruning.

It is kind of brute force solution, we like to try all combinations and then search the sum to see if it is the half.

The challenge part is to avoid time out. The idea to avoid time out is to sort numbers first, and then filter out extra search options based on current value compared to previous value.

I need to write a small case stduy to take about the analysis and design.

Run into time out limit exceeded error

The code ran into timout, and test case is [1, 1, ...., 1, 100], why it time out? Why should we skip the number if it is same as previous one?

Case study: [5, 1, 1, 1]

The idea is to sort the array first, and then start to work on depth first search. The array will be sorted as [1, 1, 1, 5], and then search a subset with sum = 4, start from index = 0.

One argument based on [1, 1, 1, 5] is that if the first integer 1 with smaller index = 0 cannot make it to find the sum, then second integer 1 will definitely not make it as well. Since the second one is subset of the previous one.

Here are highlights:

1. Work on DFS search, the idea is to sort the numbers first in order to avoid timeout;
2. Challenging task is to argue that the same integer can be skipped;
3. Only need to return true or false, no need to save the list of numbers to make the half of total sum.

I like to look into the issue why pruning is a must. Sorting takes O(NlogN) time, and then every integer can be selected or not selected, so it is O(2^N) time complexity to search the result.

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

namespace _416_partition_equal_subset_sum
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        public bool CanPartition(int[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return false;
            }

            int total = numbers.Sum();
            if (total % 2 != 0)
            {
                return false;
            }
           
            Array.Sort(numbers); // write down a few words why sorting helps

            return runDFS(numbers, 0, 0, total);
        }

        /// <summary>
        /// a few words about the design
        /// DFS - depth first search
        /// Backtracking 
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <param name="sum"></param>
        /// <param name="total"></param>
        /// <returns></returns>
        public bool runDFS(int[] numbers, int position, int sum, int total)
        {
            if (total == 2 * sum)
            {
                return true;
            }

            if (total < 2 * sum)
            {
                return false;
            }

            var result = false;
            var length = numbers.Length;

            for (int i = position; i < length; i++)
            {
                var current = numbers[i];
                if (i == position || current != numbers[i - 1])
                {
                    // add current to the selected numbers
                    result = runDFS(numbers, i + 1, sum + current, total);
                    if (result)
                    {
                        return true;
                    }                                        
                }
            }

            return false;
        }
    }
}