Backtracking | Set 4 (Subset Sum) | GeeksforGeeks

Backtracking | Set 4 (Subset Sum) | GeeksforGeeks
Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K. We are considering the set contains non-negative values. It is assumed that the input set is unique (no duplicates are presented).

Presort the arrayBy sorting the initial array, we need not to consider rest of the array, once the sum so far is greater than target number.

When we found one subset., we can generate next node excluding the present node only when inclusion of next node satisfies the constraints.

void subset_sum(int s[], int t[],

                int s_size, int t_size,

                int sum, int ite,

                int const target_sum)

{

    total_nodes++;

 

    if( target_sum == sum )

    {

        // We found sum

        printSubset(t, t_size);

 

        // constraint check

        if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )

        {

            // Exclude previous added item and consider next candidate

            subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

        }

        return;

    }

    else

    {

        // constraint check

        if( ite < s_size && sum + s[ite] <= target_sum )

        {

            // generate nodes along the breadth

            for( int i = ite; i < s_size; i++ )

            {

                t[t_size] = s[i];

 

                if( sum + s[i] <= target_sum )

                {

                    // consider next level node (along depth)

                    subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

                }

            }

        }

    }

}

    int total = 0;

    // sort the set

    qsort(s, size, sizeof(int), &comparator);

    for( int i = 0; i < size; i++ )

    {

        total += s[i];

    }

 

    if( s[0] <= target_sum && total >= target_sum ) // pre-check

    {

 

        subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

 

    }

https://algoriddles.wordpress.com/2012/04/04/kill-backtrack-sum-of-subsets-problem/
No presort:

// inputs

// s            - set vector

// t            - tuplet vector

// s_size       - set size

// t_size       - tuplet size so far

// sum          - sum so far

// ite          - nodes count

// target_sum   - sum to be found

void subset_sum(int s[], int t[],

                int s_size, int t_size,

                int sum, int ite,

                int const target_sum)

{

    total_nodes++;

    if( target_sum == sum )

    {

        // We found subset

        printSubset(t, t_size);

        // Exclude previously added item and consider next candidate

        subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

        return;

    }

    else

    {

        // generate nodes along the breadth

        for( int i = ite; i < s_size; i++ )

        {

            t[t_size] = s[i];

            // consider next level node (along depth)

            subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

        }

    }

}

http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/

public static void find(int[] A, int currSum, int index, int sum,


   int[] solution) {


  if (currSum == sum) {


   System.out.println("\nSum found");


   for (int i = 0; i < solution.length; i++) {


    if (solution[i] == 1) {


     System.out.print("  " + A[i]);


    }


   }


 


  } else if (index == A.length) {


   return;


  } else {


   solution[index] = 1;// select the element


   currSum += A[index];


   find(A, currSum, index + 1, sum, solution);


 


   solution[index] = 0;// do not select the element


   currSum -= A[index];


   find(A, currSum, index + 1, sum, solution);


  }


  return;


 }

http://www.cs.dartmouth.edu/~scot/cs10/lectures/26.5/SubsetSum.java
This only works if all numbers are non-negative.

 public static void findSubsets(List<Integer> numbers, int pos, 
   Set<Integer> subset, int sum, int target) {
  if(sum == target)
   System.out.println("Subset: " + subset);
  else if(sum < target && pos < numbers.size()) {  // Do nothing if sum already too large
   Integer m = numbers.get(pos);
   subset.add(m);
   findSubsets(numbers, pos+1, subset, sum+m, target); // Include pos
   subset.remove(m);
   
   findSubsets(numbers, pos+1, subset, sum, target);  // Don't include pos
  }
 }

http://people.cs.pitt.edu/~kirk/cs1501/codehandouts/subset.java
Read full article from Backtracking | Set 4 (Subset Sum) | GeeksforGeeks