CCI_chapter 8 Recurision

8.1 水题

8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid The robot can only move in two directions: right and down How many possible paths are there for the robot?

FOLLOW UP
Imagine certain squares are “of limits”, such that the robot can not step on them
Design an algorithm to get all possible paths for the robot

http://www.cnblogs.com/graph/p/3258531.html

http://www.cnblogs.com/graph/p/3258555.html

8.3 Write a method that returns all subsets of a set（所有子集系列）

http://www.cnblogs.com/graph/p/3216589.html

http://www.cnblogs.com/graph/p/3216496.html

8.4 Write a method to compute all permutations of a string (所有排列系列)

http://www.cnblogs.com/graph/p/3216100.html

http://www.cnblogs.com/graph/p/3215299.html

http://www.cnblogs.com/graph/p/3297845.html

http://www.cnblogs.com/graph/p/3224053.html

8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combinations of n-pairs of parentheses 

EXAMPLE:
input: 3 (e g , 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

http://www.cnblogs.com/graph/p/3194497.html

8.6   水题

8.7Given an infnite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and  pennies (1 cent), write code to calculate the number of ways of representing n cents

int a[] = {25, 10, 5, 1};
int makeChange(int n, int index)
{
    assert(index >= 0 && index <= 3);
    if(a[index] == 1) return 1;
    int way = 0;
    for(int i = 0; i * a[index] <= n; ++i)
            way += makeChange(n - i * a[index], index+1);
            
    return way;
}

8.8Write an algorithm to print all ways of arranging eight queens on a chess board so  that none of them share the same row, column or diagonal

http://www.cnblogs.com/graph/archive/2013/07/30/3226728.html