# Looking for algoritm to the partition problem C

• transgalactic
In summary, the conversation is about writing a function called partition that takes in an array of integers and determines if the array can be divided into two groups with equal sums. The function must be recursive and cannot use pointers. There is a discussion about the use of recursion in CS homework and the possibility of using other variables in the function.
transgalactic
write a function called
Code:
 int partition(int arr[], int size)
which input an array of integers and decides whether
it is possible to divide the array into two groups
so the sums of both the groups will be equal.
Code:
for example arr = {1,2,2,3,5,6,1}
its could be divided into {2,2,6}  and {1,1,3,5} both of their sums is 10
so they are equal and the function needs to return 1.

the function must be recursive without loops.
you are allowed to use only one external recursive function

and i can't use pointers
i tied to build a code that sums for ranges
but the example shows that there could be a possibility
of two sub sequences mixed with one another
so the range option is not solving this

??

Why does the method have to be recusive? Why can't you use pointers?

Because CS homework always involves recursion - CS teachers still thinks it's cool.
Fortunately almost all CS grads remember nothing they have learned so don't try and use it in the real world.

Well then, a little more coded form would help understand the task at hand. For example, since no references or pointers are allowed, how do you intend to retain a calculated value between calls...a member variable or possibly a static or global variable, or are these off limits also?

## 1. What is the partition problem in computer science?

The partition problem is a classic computational problem in computer science that involves finding a way to divide a set of integers into two subsets with equal sums. This problem has important applications in areas such as data compression, network routing, and cryptography.

## 2. What is the algorithm for solving the partition problem?

There is no single algorithm for solving the partition problem, as it is an NP-complete problem. This means that the most efficient known algorithms for solving it are exponential in time and space complexity.

## 3. How can I approach finding an algorithm for the partition problem in C?

One approach to finding an algorithm for the partition problem in C is to use a brute-force method, where you try all possible combinations of subsets and check if they have equal sums. However, this approach is not efficient for larger sets. Another approach is to use dynamic programming techniques to optimize the solution.

## 4. Are there any existing libraries or packages for solving the partition problem in C?

Yes, there are a few existing libraries and packages that offer solutions for the partition problem in C. Some popular options include the GNU Scientific Library (GSL) and the Boost C++ Libraries. These libraries offer efficient implementations of algorithms for solving the partition problem and other related problems.

## 5. How can I test the efficiency and accuracy of my partition problem algorithm in C?

To test the efficiency and accuracy of your partition problem algorithm in C, you can use a variety of standard test cases and compare your results with known solutions. You can also use specialized testing tools, such as the GNU Profiler, to analyze the performance of your algorithm and identify any potential optimizations.

Replies
22
Views
3K
Replies
2
Views
2K
Replies
17
Views
3K
Replies
1
Views
1K
Replies
19
Views
3K
Replies
1
Views
1K
Replies
45
Views
7K
Replies
9
Views
1K
Replies
2
Views
2K
Replies
2
Views
885