College of Engineering Aeronautics and Astronautics Agricultural and Biological Engineering Biomedical Engineering Chemical Engineering Civil Engineering Construction Engineering and Management Electrical and Computer Engineering Engineering Education Engineering Professional Education Environmental and Ecological Engineering Industrial Engineering Materials Engineering Mechanical Engineering Nuclear Engineering

EPICS (Engineering Projects In Community Service) First-Year Engineering Program First-Year Engineering Honors Program Global Engineering Program Minority Engineering Program Professional Practice (Co-Op) Program Women in Engineering Program

College Administration Schools Programs All Groups All People ECN Webmail


	College of Engineering \| ECN
Home Tools Demos

Purdue > Engineering > Object-Oriented Software Development > F2012 > Exercises

ECE 264 Fall 2012 Ex 7 Subset Sum (Optional)

Due Date - December 4, 2012 @ 6pm

Problem Description

Given a nonempty set S, with elements {a1, a2, a3, ...}, and a integer N, is there a nonempty subset of S, such that the sum of all elements in this subset equals to N? For example, suppose S is {1, 6, 9, 16} and N is 10. A subset of S is {1, 9} and the sum is N. If N is 11, however, we cannot find a subset of S such that the sum of the elements is N. Please remember that the elements in a set must be distinct. Please remember that an empty set is not an acceptable solution when N is 0.

In this exercise, you need to write a function that takes three arguments: an array, the size of the array, and the value N. Your function needs to determine whether it is possible to find a subset whose sum is the same as the value N. Please notice that the elements in S may be negative.

Skeleton Files

Some skeleton files are provided to help you start on writing the program. You should modify only the file ex7answer.c. The main function is provided in ipa4_main.c to handle file I/O and invokes the function subsetequal, and it also computes the time used for the funtion. The function subsetequal is to be implemented by you to actually solve the subset problem. Its prototype is provided below. You have to implement the function and not change the function interface.

int subsetequal( int * setS, int size, int numN);

It takes an integer pointer setS, which points to the location of the set array; an integer size, indicating the number of elements in the set; am integer numN, which is the integer N that will be matched against the sum of subsets of setS.
The function returns an integer value, with 1 indicating success, there is a subset whose sum equals to numN, and 0 meaning no such subset exists.

You are not permitted to modify the main function provided in the skeleton source file.

A makefile is also provide to help you compile the program and test the correctness of the program. Please modify the make file to add your own source and header file for compilation, and you can check out the make targets in the makefile or at the end of this page. Your program should be build and run under Linux, and your program is graded in Linux machines only. Please make sure your program works on the ecegrid machines.

Please check out the hints and details of the Makefile at the end of this page.

Some test cases are provided along with the skeleton file. Please type "make test".

Problem Complexity

This problem is NP-complete, meaning that currently there is no known solution to sovle it using polynomial time. If S has k elements, the worst case requires that you try every possible subset and there are 2^k subsets. We will not provide the interactive computer grader since grading your program can take a while. Please test the program before submission.