Subset Sum algorithm

I am working on this problem:

> The Subset Sum problem takes as input a set X = {x1, x2 ,…, xn} of n integers and another integer K. The problem is to check if there exists a subset X' of X whose elements sum to K and finds the subset if there's any. For example, if X = {5, 3, 11, 8, 2} and K = 16 then the answer is YES since the subset X' = {5, 11} has a sum of 16. Implement an algorithm for Subset Sum whose run time is at least O(nK).

Notice complexity O(nK). I think dynamic programming may help.

I have found an exponential time algorithm, but it doesn't help.

Can someone help me solve this problem?

Subset Sum is the first NP-complete problem I learned at Macalester. This question is viewed 36000+ times yet I don't see a sufficient answer that explains the algorithm in detail with logic. So I thought I make an attempt to do so.

Assumption:

For the sake of simplicity first I made the assumption that the input set X contains only positive integers and k is positive. However, we can tweak the algorithm to handle negative integers and the case if k is negative.

Logic:

The key to this algorithm or really any DP problem is to break down the problem and start simply from a base case. then we can build on the base case using some knowledge that we know:

1. we know that if the set X is empty then there is no way we can sum to any value of k.
2. If a set X contains k then it has a subset sum to k.
3. we know that if a subset of set x1 who is a subset of X sum to k1 then X will have a subset that sum to k1 namely x1.
4. we have a set X = {x1, x1, x3, ......., xn, xn+1}. We know it has a subset sum to k1 if x1 = {x1, x1, x3, ......., xn} has a subset sum to k - k1.

Example to illustrate 1,2,3,4:

1. it is easy. if you have an empty set {}. you can't have a subset thus you can't have any subset sum.

2. A set X = {4} has a subset sum to 4 because 4 it self is part of the set

3. say you have a set x1 = {1,3,5} who is a subset of set X = {1,3,5,2,8}. if x1 has a subset sum to k1 = 8 then that means X also has a subset sum to 8 because x1 is a subset of X

4. say you have a set X = {1,3,5,2,19} and we want to know does it have a subset sum to 20. It does and one way to can know if that is x1 = {1,3,5,2} can sum to (20 - 19) = 1. Since x1 has a subset sum to 1 then when we add 19 to the set x1 we can take that new number 1 + 19 = 20 to create our desired sum 20.

Dynamically build a matrix Cool! now let us utilize the above four logics and start building from the base case. We are going to build a matrix m. We define:

• matrix m has i+1 rows and k + 1 columns.

• Each cell of the matrix has value true or false.

• m[i][s] returns true or false to indicate the answer to this question: "using the first i items in the array can we find a subset sum to s? " m[i][s] returns true for yes and false for no

(note the Wikipedia answer or most of the people build a function m(i,s) but I thought the matrix is an easy way to understand dynamic programming. It works well when we only have positive numbers in the set or array. However the function route is better because you don't have to deal with index out of range, match index of the array and sum to the matrix.....)

Let us build the matrix using an example:

X = {1,3,5,2,8}
k = 9

We are going to build the matrix row by row. We ultimately want to know the cell m[n][k] contain true or false.

First Row: Logic 1. told us that the first row of the matrix should all be false.

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|

Second Row and above: Then for the second row or above, we can use logic 2,3,4 to help us populate the matrix.

• logic 2 tells us that m[i][s] = (X[i-1] == s) rememebr m[i] is referring to the ith item in X which is X[i-1]
• logic 3 tells us that m[i][s] = (m[i-1][s]) this is looking at the cell direclty above.
• logic 4 tells us that m[i][s] = (m[i-1][s - X[i-1]]) this is looking at the row above and left of X[i-1] cells.

If any of these is true then m[i][s] is true otherwise false. so we can rewrite 2,3,4 into m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

Use these above logics to populate the matrix m. In our example, it looks like this.

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F 
3| F T F T T T T F T T
4| F T T T T T T T T T 
5| F T T T T T T T T T

Now use the matrix to answer your question:

look at m[5][9] which is the original question. using the first 5 items (which is all the items) can we find a subset sum to 9 (k)? and the answer is indicated by that cell which is true

Here is the Code:

import java.util.*;

public class SubSetSum {

	public static boolean subSetSum(int[] a, int k){

		if(a == null){
			return false;
		}

	    //n items in the list
		int n = a.length; 
		//create matrix m
		boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0 

		//set first row of matrix to false. This also prevent array index out of bounds: -1
		for(int s = 0; s <= k; s++){
			m[0][s] = false;
		}

		//populate matrix m
		for(int i = 1; i <= n; i++){
			for(int s = 0; s <= k; s++){	
				if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bounds. (logic 4)
					m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]);	
				} else {
					m[i][s] = (m[i-1][s] || a[i-1] == s);
				}		
						
			}
		}

		//print matrix
		print(m);

		return m[n][k];

	}

	private static void print(boolean[][] m){
		for(int i = 0; i < m.length; i++){
			for(int j = 0; j < m[i].length; j++){
				if(m[i][j]){
					System.out.print("T");
				} else {
					System.out.print("F");
				}			
			}
			System.out.print("\n");
		}
	}

	public static void main(String[] args){
		int[] array = {1,3,5,2,8};
		int k = 9;

		System.out.println(subSetSum(array,k));

	}
}

To build the matrix m takes O((n+1)(k+1)) which is O(nk). it seems like it should be polynomial but it is not! It's actually pseudo polynomial. Read about it here

Again this only works if the input only contains positive numbers. You can easily tweak it to work with negative numbers tho. The matrix would still have n+1 rows but B - A + 1 columns. Where B is the upperbound and A is the lowerbound ( +1 to include zero).The matrix would still be You would have to offset s with the lowerbound.

It is pretty hard to explain DP problem over text from start to end. But I hope this helps those out there that try to understand this problem.

Note that in the examples above the rows of the DP table are sorted. That does not have to be the case.

Here is a DP table for the case of the question, i.e. given a set of {5, 3, 11, 8, 2}. For brevity, I have omitted the false values.

┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (index) │  0   │  2   │  3   │  5   │  7   │  8   │  10  │  11  │  13  │  14  │  15  │  16  │
├─────────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│    0    │ true │      │      │      │      │      │      │      │      │      │      │      │
│    5    │ true │      │      │ true │      │      │      │      │      │      │      │      │
│    3    │ true │      │ true │ true │      │ true │      │      │      │      │      │      │
│    11   │ true │      │ true │ true │      │ true │      │ true │      │ true │      │ true │
│    8    │ true │      │ true │ true │      │ true │      │ true │ true │ true │      │ true │
│    2    │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │
└─────────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

Below is an implementation in JavaScript which will output the target set {5, 11}:

var subSetSum = function(input, sum) {

    let y = input.length;
    let x = sum;

    if(input.length === 0) return 0;

    let d = [];

    //fill the rows
    for (let i = 0; i <= y; i++) {
      d[i] = [];
      d[i][0] = true;
    }
    
    for (let j = 1; j <= y; j++) { //j row
      for (let i = 1; i <= x; i++) { //i column
      let num = input[j-1];
        if(num === i) {
          d[j][i] = true;
        } else if(d[j-1][i]) {
          d[j][i] = true;
        } else if (d[j-1][i-num]) {
          d[j][i] = true;
        }
      }
    }
    
    //console.table(d); //uncomment to see the table
    if(!d[y][x]) return null;

    let searchedSet = [];
    for(let j=input.length, i=sum; j>0 && i != 0; j--) {
      if(input[j-1] !== i) {
        while(d[j-1][i]) { // go up
          j--;
        }
      }
      searchedSet.push(input[j-1]);
      i = i-input[j-1];
    }

    return searchedSet;
};

console.log('searched set:'+ JSON.stringify(subSetSum([5, 3, 11, 8, 2], 16)));

Since it looks like all your numbers are positive, you can solve this using dynamic programming:

Start will a boolean array possible of size K+1 with the first value true, the rest false. The ith value will represent whether a subset sum of i is possible to achieve. For each number n in your set, loop through the possible array and if the ith value is true, then set the i+nth value to true as well.

At the end, if the kth value in possible is true, then you can form a subset sum of k. Problem solved in O(NK) time.

Wikipedia's page on the subset sum problem has a detailed explanation of this algorithm applied to sets of integers not guaranteed to be positive.

I'd suggest to read Wiki's algorithm. The algorithm exists there, see Pseudo-polynomial time dynamic programming solution for the O(P*n) solution, The solution is not polynomial time, is polynomial in (p,n) but it's not polynomial in n+log P (size of input) and because P can be very large like 2^n, the solution P*n = (2^n)*n is not a polynomial time solution in general, but when p is bounded by some polynomial function of n is polynomial time algorithm.

This problem is NPC, but there is a Pseudo polynomial timealgorithm for it, and belongs to weakly NP-Complete problems, Also there are Strongly NP-Complete problems, which means, you can't find any pseudo polynomial time algorithm for them unless P=NP, and this problem is not in this range of problems, So somehow is easy.

I said this as simple as possible,but it's not an exact definition of a Strongly NP-Complete or Weakly NP-Complete problems.

For detail see Garey and Johnson chapter 4.

It seems I am late to the party, here are my two cents. We will create a boolean[] solution[n+1][k+1] such that solution[i][j] is true if using first i items (index 0 to i-1) we can get sum j from the set; else false. We will return solution[k][n] finally:

We can deduce the following points:

1. if sum is zero then always a possible answer (empty set) for any number of elements. So all true.
2. if set is empty we cannot have any subset hence no way to get any K. So never a possible answer. All false.
3. if a subset X1 (subset of X without last element in X) has a subset-sum for k then X also has it which is X1. E.g. for X1={1,3,5} and k=8, if X1 has a subset-sum then X={1,3,5,7} also has a subset-sum
4. For i/p set X = {1,3,5,7,19} and k=20, if X wants to know possibility of subset-sum for 20 then it does if x1={1,3,5,7} can have a subset-sum of 20-19 i.e. 1. It applies only if k >= 19 i.e. last element in X.

Based on the above points we can easily write the algorithm as below.

public class SubSetSum {
    boolean[][] solution; 
    int[] input;
    int k;

    public SubSetSum(int[] input, int targetSum) {
        this.input = input;
        this.k = targetSum;
        this.solution = new boolean[input.length+1][k+1];
    }

    public boolean subsetSum() {
        int n = input.length;

        for (int i = 0; i <= n; i++) {     //case 1
            solution[i][0] = true;
        }

        for (int j = 0; j <= k; j++) {    // case 2
            solution[0][j] = false;
        }

        for (int i = 1; i <= n; i++) {                  // n times
            for (int j = 1; j <= k; j++) {              // k times and time complexity O(n*k)
                if(solution[i-1][j]) {
                    solution[i][j] = solution[i-1][j];      // case 3
                    continue;
                }
                if(j >= input[i-1])  {                       // case 4
                    solution[i][j] = solution[i-1][j-input[i-1]];
                }
            }
        }
        return solution[n][k];
    }
}

There is no known algorithm for subset sum that runs in less than O(2^(n/2)), in the general case.

void subsetSum (int arr[], int size, int target) {
  int i, j ;
  int **table ;
  table = (int **) malloc (sizeof(int*) * (size+1)) ;
  for ( i = 0 ; i <= size ; i ++ ) {
    table[i] = (int *) malloc (sizeof(int) * (target+1)) ;
    table[i][0] = 1 ;
  }
  for ( j = 1 ; j <= target ; j ++ )
    table[0][j] = 0 ;
  for ( i = 1 ; i <= size ; i ++ ) {
    for ( j = 1 ; j <= target ; j ++ )
      table[i][j] = table[i-1][j] || (arr[i-1] <= j && table[i-1][j-arr[i-1]] ) ;
  } 
  if ( table[size][target] == 1 )
    printf ( "\ntarget sum found\n" ) ; 
  else printf ( "\nTarget sum do not found!\n" ) ;
  free (table) ;
}

let M be the sum of all the elements. Note that K<=M

let m be a Boolean array [0...M]
set all elements of m to be False
m[0]=1
for all numbers in the set let a[i] be the ith number
	for j = M to a[i]
		m[j] = m[j] | m[j-a[i]];

Then simply test for m[k]

boolean hasSubset(int arr[],int remSum,int lastElem){
	if(remSum==0) return true;
	else if(remSum!=0 && lastElem<0) return false;
		
	if(arr[lastElem]>remSum) return hasSubset(arr, remSum, lastElem-1);
	else return (hasSubset(arr, remSum, lastElem-1) ||hasSubset(arr, remSum-arr[lastElem], lastElem-1));
}

Consider i-th element. Either it will contribute for the subset sum or will not. if it contributes for the sum, then the "value of sum" is decreased by the value equal to the i-th element. If it does not contribute, then we need to search for the "value of sum" in the remaining elements.

The above answers are all great but don't really give the broadest overview of how something like this could work for both positive and negative numbers.

Given an ordered set of integers, Define two variables X and Y such that

X = sum of negative elements

Y = sum of positive elements

and operate on your initial set as if you were recursing through a binary tree by applying these rules in this order

1. If the rightmost element is equal to the sum you are trying to check for return true
2. Recurse left if doing so would not leave the empty set, drop the rightmost element from your sorted array
3. If there is one element left in your set and it is not the sum return false
4. Instead of recursing right, check the sum of all elements in the array q, if X <= B <= Y then return true, if not return false
5. If the left subtree or the right ‘recursion’ returned true then return true to the parent

The above answers are more detailed and accurate but for a very broad view of how this should play out draw a binary tree. What does the length of this suggest about the runtime?

function subsetsum(a, n) {
    var r = [];
    for (var i = parseInt(a.map(function() { return 1 }).join(''), 2); i; i--) {
        var b = i.toString(2).split('').reverse().map(function(v, i) {
            return Number(v) * a[i]
        }).filter(Boolean);
        if (eval(b.join('+')) == n) r.push(b);
    }
    return r;
}

var a = [5, 3, 11, 8, 2];
var n = 16;
console.log(subsetsum(a, n)); // -> [[3, 11, 2], [5, 3, 8], [5, 11]]

Brute force-- forget sorting, try every combo, and the eval parser beats Array.reduce (and it works with negative numbers too).

Recursive Solution with n^2 time complexity

public void solveSubsetSum(){
    int set[] = {2,6,6,4,5};
            int sum = 9;
            int n = set.length;

            // check for each element if it is a part of subset whose sum is equal to given sum
            for (int i=0; i<n;i++){
                if (isSubsetSum(set, sum, i, n)){
                    Log.d("isSubset:", "true") ;
                    break;
                }
                else{
                    Log.d("isSubset:", "false") ;
                }
                k=0; // to print time complexity pattern
            }
        }

private boolean isSubsetSum(int[] set, int sum, int i, int n) {

            for (int l=0;l<k; l++){
            System.out.print("*"); 
            // to print no of time is subset call for each element
        }
        k++;
        System.out.println();     
        if (sum == 0){
            return true;
        }
    
        if (i>=n){
            return false;
        }
    
        if (set[i] <= sum){ 
        // current element is less than required sum then we have to check if rest of the elements make a subset such that its sum is equal to the left sum(sum-current element)
            return isSubsetSum(set, sum-set[i], ++i, n);
        }
        else { //if current element is greater than required sum
            return isSubsetSum(set, sum, ++i, n);
        }
   }
    

Worst Case Complexity: O(n^2)

Best case : O(n) i.e; if first element makes a subset whose sum is equal to given sum.

Correct me if i am wrong to calculate time complexity here.

DP solution with one dimensional array(DP array processing order does matter here).

bool subsetsum_dp(vector<int>& v, int sum)
{
	int n = v.size();
	const int MAX_ELEMENT = 100;
	const int MAX_ELEMENT_VALUE = 1000;
	static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));

	dp[0] = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
		{
			if (j - v[i] < 0) continue;
			if (dp[j - v[i]]) dp[j] = 1; 
		}
	}

	return dp[sum] ? true : false;
}