Where to start for solve this exercise in c

Question

0.00/5 (No votes)

See more:

Hello I resort to your help with the intention of indicating me, what are the steps that I must follow to solve this exercise make it clear that I am not asking for the solution to the problem

Given a set {1...N} We can divide it into two subsets that their sum give the same, for example for N = 3:

C++

{1,2} = {3}

Another example with N = 7:

C++

{1,6,7} = {2,3,4,5}
{2,5,7} = {1,3,4,6}
{3,4,7} = {1,2,5,6}
{1,2,4,7} = {3,5,6}

Given an N, calculate how many ways we can make the subsets for this property is fulfilled, for N = 3 we have seen that there is a possibility; for N = 7 we have 4 possibilities. Make a recursive algorithm that solves for any 0 < N < 39.

CSS

Example input:
7
The function must be given:
3
Example input 2:
3
Example output 2
1

any aid would be welcome

edit

C#

#include<stdio.h>

int count( int S[], int m, int n )
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    if (m <=0 && n >= 1)
        return 0;
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int main(void)
{
    int arr[] = {1,6,7};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 7));
    return 0;
}

but gives me incorrect results

source: http://en.wikipedia.org/wiki/Change-making_problem[^]

Posted 12-Apr-15 11:26am

Member 11238028

Updated 12-Apr-15 14:59pm

v5

Add a Solution

Comments

PIEBALDconsult 12-Apr-15 19:50pm

"Make a recursive algorithm"
That's a bad idea.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sascha Lefèvre · Answer 1 · 2015-04-12T13:57:00

I acknowledge that you asked for the general steps to the solution and not for a ready made solution.

I assume you know what a recursive algorithm[^] is. The following is a layout for a dumb brute-force[^] recursive algorithm to solve this problem.

Set-up:
Read N from user-input.
Create a collection M for {1..N} and initialize it with these values.
Create two empty collections L and R for the two subsets.
Call the recursive method with M, L and R.

Recursion:
One method that takes as arguments:
Collection M containing the not-yet distributed values.
Collections L and R containing the already distributed values.

If M is empty:
- Sum the values in L and R.
- Compare the sums. If equal, add L and R to the valid results (e.g. print it to the console).
- Return.

Else (M is not empty):
- Take the next value x out of M.
- Insert x into L and call the recursive method with these new collections.
- Remove x from L, insert it into R and call the recursive method with these new collections.
- Remove x from R and put it back into M.
- Return.

You could make it a bit smarter by cutting some paths of the brute-force-search. E.g. for an initial M = {1,2,3,4}, at the point of the recursion where L = {1,2}, R = { } and M = {3,4} you wouldn't have to continue the recursion because ...? (The why and how left as an exercise for you.)