3 backtracking problems

[Sooth]

Hello, I have a huge list of problems but I'm having difficulties with some of them. I need algorithms for these 3 problems (pseudo-code, c++, java or c#) as I can't find solutions for them:


1. For a set of n integer elements, generate all the subsets of that set that have the sum of all their elements an odd number.

2. Generate all the decompositions of a natural number n in sums of prime numbers.

3. For a given integer, n, generate all the growing functions f : {1, 2, 3, ..., n} -> {1, 2, 3, ..., n} with the property: f(x)<=x for any x in {1, 2, ..., n}.


Any help is appreciated! Thank you.

[BioPhysEngr]

These appear to be homework problems, so I won't provide their solutions. I am, however, happy to explain how backtracking works. Algorithms that find solutions to constraint problems by backtracking all work by constructing a solution and at each step in the construction check to make sure that no constrains prevent further construction. If they are, it goes back a step and tries a different construction. For example:

Suppose you have for workers who can each work on the following days of the week, and only one worker may work on any given day:


Alice MTWR
Bob TW
Carl M W
Dory MT


A backtracking algorithm to assign them days to work would execute as follows:
(1) Start with Alice and assign her to work on the Monday (the first option)
(2) Check: Does everyone else still have a day they can work on? Yes.
(3) Assign Bob (2nd person in the list) to work on Tuesday.
(4) Check: Does everyone still have a day they can work on? No, Dory cannot, so...
(5) Backtrack: Assign Bob to work on the next day available instead (Wednesday)
(6) Check: Does everyone still have a day they can work on? No, Carl cannot, so...
(7) Backtrack: Assign Bob to work on the next day available for him, but - oh no - he is out of days to work, so...
(8) Backtrack: Assign Alice to the next day to work (Tuesday).
(9) Continue with Bob... The algorithm flow should be clear by now...

Does that help? You should be able to apply the 'construct solution and check constrains at each step' procedure to your problems. For more information, I recommend Russell and Norvig's excellent book on Artificial Intelligence (http://aima.cs.berkeley.edu/) or the Backtracking Wikipedia page (http://en.wikipedia.org/wiki/Backtracking) or this tutorial (http://www.cs.rpi.edu/~hollingd/psics/notes/backtracking.pdf).

I hope that gets you started!

[BioPhysEngr]

I should also add that you can get better performance out of backtracking solutions if you try to make assignments to the most constrained choices first. In my example, that means assigning days to Bob, Carl or Dory (because they each have 2 possible days they can work) before assigning Alice (since she is the least constrained). This makes sense and is how you would do this in your head: 'Okay, Let Dory have Monday, and that'd mean Carl'd have to work Wednesday (b/c now Carl is only one option left after the assignment to Dory we assigned him after Dory), ....'

If you want to program for fun, backtracking algorithms are popular ways of solving Sodoku puzzles programatically.