Algorithm for sum in array

I’m trying to find out if the sum of any elements in array is equal to a certain sum.

Example: {2, 1, 2, 4, 3, 5, 2, 6}, S = 14  yes (1 + 2 + 5 + 6 = 14)

I tried to find solution in the internet but coudn’t see any. Help appreciated!

EDIT: I found a solution that works best for me and it’s relatively short there it is for everybody who is interested in seeing what I’ve found.

private bool IsPossible()
    {
        string subset = "";

        int maxSubsets = (int)System.Math.Pow(2, numbers.Length) - 1;
        for (int i = 1; i <= maxSubsets; i++)
        {
            subset = "";
            long checkingSum = 0;
            for (int j = 0; j <= numbers.Length; j++)
            {
                int mask = 1 << j;
                int nAndMask = i & mask;
                int bit = nAndMask >> j;
                if (bit == 1)
                {
                    checkingSum = checkingSum + numbers[j];
                    subset = subset + " " + numbers[j];
                }
            }
            if (checkingSum == MainNumber)
            {
                return true;
            }
        }

        return false;
    }

numbers is the array with the numbers and MainNumber is the sum we’ve got to find.
Cheers and thanks to everybody who responded nicely!

This can be seen as the famous (0-1) Knapsack problem.
Google this term or simply look at the suggested algorithm on Knapsack problem - Wikipedia

Well, i had some time so i quickly implemented a class that can do what you want :wink:

using UnityEngine;
using System.Collections;
using System.Linq;
using System.Collections.Generic;
using Stopwatch = System.Diagnostics.Stopwatch;

public class CombinationFinder
{
    Stopwatch m_Stopwatch = new Stopwatch();
    List<int> m_Values;
    int m_TotalSum;
    public System.TimeSpan TimeTaken { get { return m_Stopwatch.Elapsed; } }

    public CombinationFinder(IEnumerable<int> aValues)
    {
        m_TotalSum = aValues.Sum();
        m_Values = aValues.OrderByDescending(v => v).ToList();
    }
    public CombinationFinder(params int[] aValues) : this(aValues as IEnumerable<int>){ }

    IEnumerable<int> FindCombinationStep(int aSum, int aTotalSum, int aStart)
    {
        if (aTotalSum == aSum)
            return m_Values.Skip(aStart);
        if (aTotalSum < aSum)
            return null;
        for (int i = aStart; i < m_Values.Count; i++)
        {
            aTotalSum -= m_Values*;*

if (i > aStart && m_Values[i - 1] == m_Values*)
continue;
int newSum = aSum - m_Values;
if (newSum == 0)
return Enumerable.Range(m_Values, 1);
if (newSum < 0)
continue;
var res = FindCombinationStep(newSum, aTotalSum, i + 1);
if (res == null)
continue;
return Enumerable.Range(m_Values, 1).Concat(res);
_}
return null;
}*_

public int[] FindCombination(int aSum)
{
m_Stopwatch.Reset();
m_Stopwatch.Start();
var result = FindCombinationStep(aSum, m_TotalSum, 0);
int[] array = null;
if (result != null)
array = result.ToArray();
m_Stopwatch.Stop();
return array;
}
}
Usage:
//C#
void RunTest()
{
var finder = new CombinationFinder(50, 2, 4, 6, 3, 5, 2, 7,10,55,800,40,20,15,18,17,23,25,29,40);
for (int i = 0; i < 1000; i++)
{
var res = finder.FindCombination(i);
if (res != null)
Debug.Log(“# " + i + " = " + string.Join(” + ", res.Select(a => a.ToString()).ToArray()) + " Time: " + finder.TimeTaken.TotalMilliseconds * 1000 + “µs”);
else
Debug.LogError("# " + i + " — " + " Time: " + finder.TimeTaken.TotalMilliseconds * 1000 + “µs”);
}
}
This test routine will try to find a combination with the given 20 numbers for every number between 0 and 1000 and prints the result. Note: On my PC each FindCombination call usually took something under 10µs. If there are spikes it’s most likely due to task switch / core switch (damn multitasking :D). The over all time for those 1000 calls is about 2 sec but only because of the Debug.Logs which are about 98% of that time :smiley:
I used a hybrid of recursive and iterative approach. So it actually iterates through the (sorted) list. If (theDesiredSum - theCurrentValue ) is still larger than 0, it will start a new recursion on the remaining sum and the remaining list values. There are a lot optimisations in each recursion step to terminate early when possible. For example when the list contains the same number multiple times and it doesn’t work out when using the first, it makes no sense to use the others at the same place since all combinations below this value has already been checked.
Example:
Sum = 27
values = 11, 11, 11, 11, 11, 10, 10, 4, 3
recur.
#1: 11 → remaining 16
#2: 11+ 11 → remaining 5
#3: 11+ 11+ 11 → fail
#3: 11+ 11+ – – – 10 → fail
#3: 11+ 11+ – – – – – 4 → remaining 1
#4: 11+ 11+ – – – – – 4+ 3 → fail
#2: 11+ – – – – 10 → remaining 6
#3: 11+ – – – – 10+ 10 → fail
#3: 11+ – – – – 10+ – 4 → remaining 2
#4: 11+ – – – – 10+ – 4+ 3 → fail
#2: → fail due to not enough values remaining
#1: – – – – – 10 → remaining 17
#2: → solution since remaining sum == sum
#2: returns → 10, 4, 3
#1: returns → 10, 10, 4, 3
The -- indicates a skipped number.
edit Just realized i had the 3 and 4 swapped in my example ^^ fixed it.

The easiest best fit algorithm that I know of is to:

  1. Sort your list to be in descending order (highest to lowest)
  2. Create a sum variable
  3. Iterate through the sorted list and add the highest number to the sum that means it is still less than or equal to your target.
  4. Keep going until you either reach the target or you have not reached it but have run out of elements.
  5. Return true or false depending on the above out come.

Here’s a very quick and dirty implementation of that algorithm, I’m pretty sure this could be made more efficient by combining lists used or for loops etc!

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class bestFit : MonoBehaviour {
	public int[] ints;
	public int target;
	
	void Update(){
		if(Input.GetKeyDown(KeyCode.R)){
			Debug.Log(CanFit(ints, target));
		}
	}
	
	bool CanFit(int[] iArray, int t){
		List<int> iList = new List<int>();
		for(int a = 0; a < iArray.Length; a++){
			iList.Add(iArray[a]);
		}
		int[] sortedArray = new int[iArray.Length];
		for(int i = 0; i < iArray.Length; i++){
			int size = int.MinValue;
			int index = 0;
			for(int j = 0; j < iList.Count; j++){
				if(iList[j] > size){
					size = iList[j];
					index = j;
				}
			}
			sortedArray *= iList[index];*
  •  	iList.RemoveAt(index);*
    
  •  }*
    
  •  int sum = 0;*
    
  •  string sumBackground = "";*
    
  •  for(int m = 0; m < sortedArray.Length; m++){*
    
  •  	if(sum + sortedArray[m] > t){*
    
  •  		continue;*
    
  •  	}else if(sum + sortedArray[m] == t){*
    
  •  		sumBackground += sortedArray[m].ToString();*
    
  •  		Debug.Log(sumBackground);*
    
  •  		return true;*
    
  •  	}else{*
    
  •  		sum += sortedArray[m];*
    
  •  		sumBackground += sortedArray[m].ToString() + " + ";*
    
  •  		continue;*
    
  •  	}*
    
  •  }*
    
  •  return false;*
    
  • }*
    }