经典递归题目与解答

一、输入{[2,3,6,7], 7}，输出{[2,2,3], [7]}。解释：从数组中选取和是给定值的组合，数组元素是不重复的正整数。

令K代表当前的差距，A代表当前可选择数字序列的起始位置，N代表从A开始有多少个数字可供选择。那么只需要不断选择一个数字，更新A,N,K，然后再选一个数，直到K=0，说明找到了一个序列。 

F（A,N,K）
　　IF K = 0：Accept tmp[] and return
　　FOR T←[N..A.Length], step←1：
　　　　IF A[T] <= K：
　　　　　　tmp.APPEND A[T]
　　　　　　F(A, T, K-A[T])
　　　　　　tmp.POP
　　　　FI

二、输入2，输出{()(), (())}。解释：计算N组括号的有效组合。

序列中的一个位置要么是左括号，要么是右括号。用辅助函数_F(L,R)指明需要从当前位置写入L个左括号和R个右括号，主过程F调用_F(N,N)。L>R说明括号不匹配。R=0则接受序列。然后根据L和R的关系选择该处可以是左括号还是右括号。

_F(L, R)：
　　IF  R＝0：Accept and return
　　IF  L > 0：save X;　buf[X++] ← '(';　　 _F(L-1,R);　　restore X;
　　IF  R > L：buf[X++] ← ')';　　 _F(L, R-1)
F(N)： _F(N,N)

性能：N=17时用时3.64秒，还行吧。

三、N皇后问题。N小于10。

假设前M-1行已经放置了皇后Q[1..m-1]，现在要向第M行放置皇后Q[m]。将Q[m]依次放到第M行的各列，检查Q[m]是否和Q[1..m-1]冲突，若不冲突则向第M+1行放置Q[m+1]。以此类推，直到发现M>N。

_F(M, N)：
　　IF  M>N ：Accept and return
　　FOR S←[1..N] step←1：
　　　　PUT(Q_m, M,S)
　　　　IF OK：_F(M+1, N)
　　　　PICKUP(Q_m)
F(N)： _F(0, N)

四、全排列。给定含有N个不重复整数的序列A，计算其所有排列方式。 

F(A,N)：
　　IF (X = N)： Accept and return
　　FOR S←[0..N] step←1：
　　　　IF 0=visited[S]：
　　　　　　buf[X++] ← A[S]
　　　　　　set visited[S]，F(A, N)，clear visited[S]
　　　　　　X←X-1
　　　　FI

五、幂集。输入A={a,b,c}，输出A`={{a,b,c},{a,b},{b,c},{a,c},{a},{b},{c},Φ}。 

F(A,N)：
　　IF N=0：Accept and return
　　buf[X] ← A[N-1]
　　X←X+1，F(A, N-2)
　　X←X-1，F(A, N-2)