Find Combination(S) Sum of Element(S) in Array Whose Sum Equal to a Given Number

Find combination(s) sum of element(s) in array whose sum equal to a given number

The problem is NP-Hard. Even determining if there is ANY subset of the problem that sums to the desired number is NP-Hard (known as the subset sum problem), and there is no known polynomial solution to it.

Thus, you should look for an exponantial solution, such as a backtracking one - generate all possible combinations, and check if they are valid.

You can use trimming to get your search faster (for example, if you generate a partial subset of sum 13, no need to check other subsets which are supersets of this subset, since they will definetly won't lead to a solution.

pseudo code:

findValidSubsets(sum,arr,idx,currSolution):
   if (sum == 0):
       print currSolution
   if (sum < 0): //trim the search, it won't be succesful
       return
   //one possibility: don't take the current candidate
   findPermutations(sum,arr,idx+1,currSolution) 

   //second poassibility: take the current candidate
   currSolution.add(arr[idx])
   findPermutations(sum-arr[idx],arr,idx+1,currSolution)

   //clean up before returning: 
   currSolution.removeLast()

Complexity is O(2^n) - need to generate at worst case all 2^n possible subsets

Invoke with findValidSubsets(desiredSum,myArray,0,[]), where [] is an empty initial list

Finding all possible combinations of numbers to reach a given sum

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue
    
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 
   

if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

This type of algorithms are very well explained in the following Stanford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.

Edit

The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Here is the Java version of the same algorithm:

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.

C# conversion of Java solution: (by @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby solution: (by @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: complexity discussion

As others mention this is an NP-hard problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.

On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.

If N and Target are big numbers one should move into an approximate version of the solution.

Finding all possible combinations of numbers of an array to reach a given sum

Took me while to code this. So it's basically brute force. I recursively (backtracking) generate all possible expression with the operators given and then evaluate them. Note these are just infix expression(s).

Now this is a very slow solution. There are several optimization one can do here.

vector<string> allCombinations(vector<int> &arr, int k)
{
    int n = (int)arr.size();
    string operators = "+-*";
    vector<string> ans;
    // To check precedence of operators
    auto prec = [&](char op) -> int
    {
        if (op == '*' or op == '/') return 2;
        if (op == '+' or op == '-') return 1;
        return -1;
    };
    // For infix evaluation (kindof a helper function)
    auto compute = [&](int v1, char op, int v2) -> int
    {
        if (op == '+') return v1 + v2;
        if (op == '-') return v1 - v2;
        if (op == '*') return v1 * v2;
        if (op == '/') return v1 / v2;
        assert(false);
        return INT_MAX;
    };
    // Main infix evaluation function
    auto evaluate = [&](string s) -> int
    {
        int len = (int)s.size();
        // vector is being used as a STACK
        vector<int> val;
        vector<char> ops;
        for (int i = 0; i < len; i++)
        {
            char curr = s[i];
            if (curr == ' ') continue;
            if (isdigit(curr))
            {
                int v = 0;
                while (i < len and isdigit(s[i])) v = 10 * v + (s[i++] - '0');
                val.push_back(v);
                i--;
            }
            else
            {
                while (!ops.empty() and prec(curr) <= prec(ops.back()))
                {
                    int v1 = val.back();
                    val.pop_back();
                    int v2 = val.back();
                    val.pop_back();
                    char op = ops.back();
                    ops.pop_back();
                    val.push_back(compute(v2, op, v1));
                }
                ops.push_back(curr);
            }
        }
        while (!ops.empty())
        {
            int v1 = val.back();
            val.pop_back();
            int v2 = val.back();
            val.pop_back();
            char op = ops.back();
            ops.pop_back();
            val.push_back(compute(v2, op, v1));
        }
        return val.back();
    };
    // Generates all expression possible
    function<void(int, string&)> generate = [&](int i, string &s) -> void
    {
        s += to_string(arr[i]);
        if (i == n - 1)
        {
            if (evaluate(s) == k) ans.push_back(s);
            // Backtrack
            s.pop_back();
            return;
        }
        for (char &ops : operators) 
        {
            s.push_back(ops);
            generate(i + 1, s);
            // Backtrack
            s.pop_back();
        }
        // Backtrack
        s.pop_back();
    };
    string s;
    // Try all combinations
    sort(arr.begin(), arr.end());
    do
    {
        generate(0, s);
    } while (next_permutation(arr.begin(), arr.end()));
    return ans;
}

Find Distinct parts of List that Sum are equal to the given Number

Your original function was generating properly the possible combinations. The only problem was that you were printing it, instead of saving it in a list to use later.

I modified it so it saves the result into a list, that can be input to a function that generates all permutations (also implemented recursively) of a list.

Overall, the approach is:

1. Generate all combinations of 1, 2, ... n numbers that sum to less than goal
2. Generate all the permutations of these combinations (this step seems useless, because sum is commutative, but I'm assuming that is the definition of your problem)

Note that this is an instance of the Subset Sum Problem, which is a difficult optimisation problem. The solution below does not scale well for large sets.

def unique_combination(in_list, goal, current_sum, current_path, accumulator):
    # Does a depth-first search of number *combinations* that sum exactly to `goal`
    # in_list is assumed sorted from smaller to largest

    for idx, current_element in enumerate(in_list):
        next_sum = current_sum + current_element
        if next_sum < goal:
            next_path = list(current_path)  # list is needed here to create a copy, as Python has a pass by reference semantics for lists
            next_path.append(current_element)
            unique_combination(in_list[idx+1:], goal, next_sum, next_path, accumulator)
        elif next_sum == goal:  # Arrived at a solution
            final_path = list(current_path)
            final_path.append(current_element)
            accumulator.append(final_path)
        else:   # Since in_list is ordered, all other numbers will fail after this
            break
    return accumulator

def permutations(elements):
    # Returns a list of all permutations of `elements`, calculated recursively
    if len(elements) == 1:
        return [elements]
    result = []
    for idx, el in enumerate(elements):
        other_elements = elements[:idx] + elements[idx+1:]
        all_perms = [[el] + sub_perms for sub_perms in permutations(other_elements)]
        result.extend(all_perms)
    return result

def myFunc(input_list, goal):
    # Sort the given elements
    input_list.sort()
    combinations = unique_combination(input_list, goal, 0, [], [])

    result = []
    for comb in combinations:
        result.extend(permutations(comb))
    return result

def print_results(results):
    for el in results:
        print(tuple(el)) # to get the parentheses

# Input:
a = [1,2,3,4,6,7,8]
k = 8
all_permutations = myFunc(a, k)
print_results(all_permutations)

# (1, 3, 4)
# (1, 4, 3)
# (3, 1, 4)
# (3, 4, 1)
# (4, 1, 3)
# (4, 3, 1)
# (1, 7)
# (7, 1)
# (2, 6)
# (6, 2)
# (8,)

How to count all numeric array elements combinations whose sum is equal to a given value?

You could take a recursive call by avoiding built in array methods (iteration and most expensive slicing) and take a recursive function which get an index for the next number to get, an array of collected values and a new target, without the last taken value.

This approach returns all possible values, they are not unique, depending on the given data. This approach works for positive numbers only.

function subsetSum(numbers, target) {    function iter(index, right, delta) {        if (!delta) return result.push(right);        if (index >= numbers.length) return;        if (delta - numbers[index] >= 0)            iter(index + 1, [...right, numbers[index]], delta - numbers[index]);        iter(index + 1, right, delta);    }    var result = [];    iter(0, [], target);    return result;}
subsetSum([1, 1, 2, 2, 3, 7, 9, 1], 7).map(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

# Let arr be the given array.
# And K be the give sum


for i=0 to arr.length - 1 do
  # key is the element and value is its index.
  hash(arr[i]) = i  
end-for

for i=0 to arr.length - 1 do
  # if K-th element exists and it's different then we found a pair
  if hash(K - arr[i]) != i  
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

{initial: {a: 1, b: 2, c: 1}, last: {d: 3}}

{initial: {b: 2, c: 1, e: 2}}

// utility functions
const last = (xs) => 
  xs [xs .length - 1]

const partitions = (xs) => 
  xs .length === 0
    ? [[[], []]]
    : partitions (xs .slice (0, -1)) .flatMap (([p, q]) => [ 
        [[...p, last (xs)], q], 
        [p, [...q, last (xs)]] 
      ])

// helper function
const total = (xs) =>
  xs .reduce ((a, [k, v]) => a + v, 0)


// main function
const sumTo = (n, xs, parts = partitions (xs)) =>
  parts .flatMap (([incl, excl], _, __, t = total (incl)) => [
    ... (t == n ? [{initial: incl}] : []),
    ... (t < n
           ? excl .filter (([k, v]) => v + t > n) 
                  .map (e => ({initial: incl, last: [e]}))
           : []
        )
  ])


// public function
const subsetSum = (n, dict) =>
  sumTo (n, Object.entries (dict))
    .map (({initial, last}) => ({
      initial: Object .fromEntries (initial), 
      ... (last ? {last: Object .fromEntries (last)} : {})
    }))


// sample data
const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}


// demo
console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}