-3

I have 65 numbers in an array example: [1,2,3,4,5.....65]. I have a value in another variable. example: 10. I want to find which numbers I have to sum from the array to get that number in the varaible. In this example it is 2+3+5 = 10. Is there any pseudo code or any c# code available for that?

Regards, Joe

Joe Samraj
  • 311
  • 3
  • 21
  • can you only add? Or Subtract too? – UserID0908 Jan 20 '18 at 06:18
  • https://stackoverflow.com/questions/16604985/find-elements-in-a-list-that-together-add-up-to-a-target-number, Refer this link @Joe Samraj – Saravanakumar Natarajan Jan 20 '18 at 06:19
  • @UserID0908 only add – Joe Samraj Jan 20 '18 at 06:40
  • 1
    This is the famous subset sum problem. At least you should try to solve it yourself first... For this example it can be done much more efficiently. – user202729 Jan 20 '18 at 07:20
  • Sorry for the delay. Thanks @user202729 for directing me in the right path. I got a code here https://kunuk.wordpress.com/2012/12/25/backtracking-subset-sum-with-c/ which is good in performance. – Joe Samraj Feb 12 '18 at 05:51
  • Sorry for the delay. Thanks @Saravanakumar for your reference. I got a code here https://kunuk.wordpress.com/2012/12/25/backtracking-subset-sum-with-c/ which is good in performance. – Joe Samraj Feb 12 '18 at 05:52

1 Answers1

0

I have a small class for you. I hope, it helps :)

Here the program:

var finder = new NumbersForTotalFinder(Enumerable.Range(1, 65));
var results = finder.Find(10);
Debug.Assert(results.All(a => a.Sum() == 10));

and here the finder

class NumbersForTotalFinder
{
    public NumbersForTotalFinder(IEnumerable<int> numbers)
    {
        _numbers = numbers.OrderBy(n => n).ToArray();
    }

    public List<int[]> Find(int total)
    {
        var results = new List<int[]>();
        var temp = new int[_numbers.Length];

        for (var index = 0; index < _numbers.Length; index++)
        {
            var num = _numbers[index];
            temp[0] = num;
            if (num == total)
            {
                SaveResult(results, temp, 1);
            }
            if (num >= total)
            {
                break;
            }
            Check(index + 1, 1, num, total, results, temp);
        }

        return results;
    }

    private void Check(int index, int depth, int sum, int total, List<int[]> results, int[] temp)
    {
        while (index < _numbers.Length)
        {
            var newNum = _numbers[index];
            var newSum = sum + newNum;

            if (newSum > total)
            {
                break;
            }

            temp[depth] = newNum;
            if (newSum == total)
            {
                SaveResult(results, temp, depth + 1);
                break;
            }

            Check(index + 1, depth + 1, newSum, total, results, temp);
            index++;
        }
    }

    private void SaveResult(List<int[]> results, int[] temp, int length)
    {
        var newResult = new int[length];
        Array.Copy(temp, newResult, length);
        results.Add(newResult);
    }

    private int[] _numbers;
}
Georg
  • 1,946
  • 26
  • 18
  • Sorry for the delay, But Thanks for your help. The above code is taking much time on bigger numbers and long array. https://kunuk.wordpress.com/2012/12/25/backtracking-subset-sum-with-c/ This works with bigger numbers and long array – Joe Samraj Feb 12 '18 at 05:21