Take the 2-minute tour ×

Let's say I have {3, 1, 1, 2, 2, 1, 5, 2, 7} set of numbers, I need to split the numbers such that sum of subset1 should be equal to sum of subset2 {3,2,7} {1,1,2,1,5,2}. First we should identify whether we can split number(one way might be dividable by 2 without any remainder) and if we can, we should write our algorithm two create s1 and s2 out of s.

How to proceed with this approach? I read partition problem in wiki and even in some articles but I am not able to get anything. Can someone help me to find the right algorithm and its explanation in simple English?

share|improve this question
You'll get a Nobel Prize (Turing Award) if you solve this for "any" set of numbers. If I'm right, this is Number Partitioning and is NP-Complete :) –  PhD Jun 16 '12 at 18:57
This is not an easy problem. Look into "linear programming" or/and "constraint programming". With regards to the letter: I think this problem could be relatively easily modelled in Mozart/Oz. –  wmeyer Jun 16 '12 at 19:03

3 Answers 3

As @wmeyer noticed, this problem can be stated quite nicely using Constraint Programming. And this simple problem instance is easily solved.

First, here is a high level model written in MiniZinc which is basically this code, without the output section. (See http://www.hakank.org/minizinc/partition_into_subset_of_equal_values.mzn for the full model.)

% problem instance and its length
array[1..n] of int: s = [3, 1, 1, 2, 2, 1, 5, 2, 7];
int: n = 9;

% number of subsets
int: num_subsets = 2;

% the decision variables
% to which subset does x[i] belong?
array[1..n] of var 1..num_subsets: x;

solve satisfy; % we want all solutions

% Constraints

% Ensure that the sum of the subsets are the same
   forall(p in 1..num_subsets-1) (
      sum([s[i]*bool2int(x[i] == p) | i in 1..n]) == 
      sum([s[i]*bool2int(x[i] == p+1) | i in 1..n])

% symmetry breaking: assign the first number to subset 1
constraint x[1] = 1;

Since the question is tagged "C#", here's model using the C# interface of Google or-tools (with a little different approach than the MiniZinc model): http://www.hakank.org/google_or_tools/partition_into_subsets_of_equal_values.cs

Note: For the given numbers - and using the symmetry breaking of assigning the first number to subset 1 - there are 19 different partitions (solutions) with 2 subsets, and 42 different partitions when using 3 subsets. For 4 subset there is no solution.

share|improve this answer
Some more about performance: I've tested the MiniZinc model with 100 and 1000 random integers in the range 1..10 (1..100): the first solution is shown in a few milliseconds. For 10000 random integers (in the range 1..10) then it took a little bit longer: about 3 seconds after about 20 seconds of generating the intermediate FlatZinc format. This variant is here: hakank.org/minizinc/partition_into_subset_of_equal_values2.mzn (it's 28kB). –  hakank Jun 17 '12 at 18:32
And this C# version (hakank.org/or-tools/partition_into_subsets_of_equal_values2.cs) solves the problem with 100000 random integers (in the ranges of 1..10, 1..100 as well as 1..1000) in about 3 seconds. –  hakank Jun 17 '12 at 19:10

As somebody commented, this problem is isomorphic to “subset sum”, and so it’s NP-complete. Basically, the naive solutions to this problem are the best solutions and they’re very, very bad. :) I only say this so you don’t look for a more “optimized” version or something.

share|improve this answer
In general, this is an NP-complete problem. For small-ish integers it is solvable by dynamic programming in time that is polynomial in the sum of the inputs. –  kevin cline Jun 17 '12 at 17:37
using System;
using System.Linq;
public class CandidateCode
    public static string partition(int[] input1)
        bool[] best_assignment = PartitionValues(input1);

        string result1 = "", result2 = "";
        int total1 = 0, total2 = 0;
        for (int i = 0; i < best_assignment.Length; i++)
            if (best_assignment[i])
                result1 += "\r\n " + input1[i];
                total1 += input1[i];
                result2 += "\r\n " + input1[i];
                total2 += input1[i];
        if (result1.Length > 0) result1 = result1.Substring(2);
        if (result2.Length > 0) result2 = result2.Substring(2);

        return "{"+ result1 + " } {" + result2 + " } total  " + total1.ToString() + " & " + total2.ToString();

    private static bool[] PartitionValues(int[] values)
        bool[] best_assignment = new bool[values.Length];
        bool[] test_assignment = new bool[values.Length];

        int total_value = values.Sum();

        int best_err = total_value;
        PartitionValuesFromIndex(values, 0, total_value, test_assignment, 0, ref best_assignment, ref best_err);

        return best_assignment;

    private static void PartitionValuesFromIndex(int[] values, int start_index, int total_value,
            bool[] test_assignment, int test_value,
            ref bool[] best_assignment, ref int best_err)
        // If start_index is beyond the end of the array,
        // then all entries have been assigned.
        if (start_index >= values.Length)
            // We're done. See if this assignment is better than what we have so far.
            int test_err = Math.Abs(2 * test_value - total_value);
            if (test_err < best_err)
                // This is an improvement. Save it.
                best_err = test_err;
                best_assignment = (bool[])test_assignment.Clone();
            // Try adding values[start_index] to set 1.
            test_assignment[start_index] = true;
            PartitionValuesFromIndex(values, start_index + 1, total_value,
                test_assignment, test_value + values[start_index],
                ref best_assignment, ref best_err);

            // Try adding values[start_index] to set 2.
            test_assignment[start_index] = false;
            PartitionValuesFromIndex(values, start_index + 1, total_value,
                test_assignment, test_value,
                ref best_assignment, ref best_err);
share|improve this answer

Your Answer


