Thread: Find all subsets with sum of x

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    117

    Find all subsets with sum of x

    Hello,

    I am working on a homework lab in which we have to find all the subsets equal to a given sum from an array of numbers.

    For example, an array of 7 numbers (1, 3, 4, 6, 7, 10, 25) with a sum of 25 would be (1, 3, 4, 7) and (25)

    We are supposed to use dynamic programming to solve this.
    Now using the code below that we went over in class (Sedgewick's subsetSum), I understand how to this finds the first subset that adds up to the sum given. What's stumping me is how to find multiple subsets.

    Code:
    main(){
    // Get input sequence
    int n;    // Size of input set
    int m;    // Target value
    int *S;   // Input set
    int *C;   // Cost table
    int i,j,potentialSum,leftover;
    
    
    scanf("%d",&n);
    scanf("%d",&m);
    
    
    S=(int*) malloc((n+1)*sizeof(int));
    C=(int*) malloc((m+1)*sizeof(int));
    if (!S || !C)
    {
      printf("malloc failed %d\n",__LINE__);
      exit(0);
    }
    
    
    S[0]=0;                // Sentinel zero
    for (i=1;i<=n;i++)
      scanf("%d",S+i);
    
    
    // Initialize table for DP
    C[0]=0;  // DP base case
    // For each potential sum, determine the smallest index such
    // that its input value is in a subset to achieve that sum.
    for (potentialSum=1; potentialSum<=m; potentialSum ++)
    {
      for (j=1;j<=n;j++)
      {
        leftover=potentialSum-S[j];      // To be achieved with other values
        if (leftover<0)                  // Too much thrown away
          continue;
        if (C[leftover]==(-1))           // No way to achieve leftover
          continue;
        if (C[leftover]<j)               // Indices are included in
          break;                         // ascending order.
      }
      
      if (j<=n)
         C[potentialSum]=j;
      else
          C[potentialSum]=-1;
    
    
    }
    
    
    /**/
    // Output the input set
    printf("  i   S\n");
    printf("-------\n");
    for (i=0;i<=n;i++)
      printf("%3d %3d\n",i,S[i]);
    
    
    // Output the DP table
    printf("  i   C\n");
    printf("-------\n");
    for (i=0;i<=m;i++)
      printf("%3d %3d\n",i,C[i]);
    /**/
    
    
    if (C[m]==(-1))
      printf("No solution\n");
    else
    {
      printf("Solution\n");
      printf("  i   S\n");
      printf("-------\n");
      for (i=m;i>0;i-=S[C[i]])
        printf("%3d %3d\n",C[i],S[C[i]]);
    }
    }
    For example if given the set I listed earlier (1, 3, 4, 6, 7, 10, 25) and sum of 25, the output I would need to give would be as follows:

    Solution with 1 elements
    i S
    -------
    7 25
    No solution with 2 elements
    No solution with 3 elements
    No solution with 4 elements
    Solution with 5 elements
    i S
    -------
    6 10
    5 7
    3 4
    2 3
    1 1
    No solution with 6 elements
    No solution with 7 elements

    Can anyone give me an idea of which direction to go on this? In class the teacher said it would be mainly just modifying the code we went over in class. Any input would be appreciated. Not asking for anyone to code this/do this for me, but just give me any ideas on where to start on this.

    Thanks!

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Read this, and see if it helps. There is a section on dynamic programming to solve it, as well.

    Subset sum problem - Wikipedia, the free encyclopedia

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. subsets filling the gaps question..
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 07-06-2009, 04:51 AM
  2. How to do array subsets?
    By gormster in forum C Programming
    Replies: 5
    Last Post: 11-14-2007, 06:50 AM
  3. Subsets of binary string
    By damonbrinkley in forum C Programming
    Replies: 4
    Last Post: 05-03-2005, 09:00 AM
  4. compute the subsets of a set
    By k_w_s_t_a_s in forum C Programming
    Replies: 4
    Last Post: 06-01-2003, 05:54 PM
  5. subsets
    By scottmanc in forum C++ Programming
    Replies: 7
    Last Post: 03-11-2003, 08:22 AM