recursive solution for subset sum , C#

recursive solution for subset sum

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        //recursive solution for subset sum 
        public static void Main(string[] args)
        {
            int[] values = { 3, 34, 4, 12, 5, 2 }; 
            int sum = 46; 
            int n = values.Length; 
            if (isSubsetSum(values, n, sum) == true) 
                Console.WriteLine("Found a subset with given sum"); 
            else
                Console.WriteLine("No subset found for given sum"); 
        }
        
        // Returns true if sum of sub ser is equal to given sum 
        static bool isSubsetSum(int[] values, int n, int sum) 
        { 
            // Base Cases - if sum is 0, it is true
            if (sum == 0) {
                return true; 
            }
            //if there are no values, retrun false
            if (n == 0 && sum != 0) {
                return false; 
            }

// If last element is greater than sum, then ignore it 
            if (values[n - 1] > sum) 
                return isSubsetSum(values, n - 1, sum);

/* else, check if sum can be obtained  by any of the following 
            (a) including the last element 
            (b) excluding the last element */
            return isSubsetSum(values, n - 1, sum)  
                  || isSubsetSum(values, n - 1, sum - values[n - 1]); 
        } 
    }
}


run \| edit \| history \| help	0